2
$\begingroup$

I want to test if someone with no experience in Graph Theory can solve my Problems involving Graphs. If you do know some Graph Theory I'd appreciate if you let me know in your answer.

They do not require high-level knowledge or understanding.

If you would like to see more examples of these Problems, to help you work out what to do, please check out my other posts. (What's the question to this and what is its answer?)

(These are two separate problems.)

I normally use this reference system for the panels: enter image description here

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Is this two different problems? $\endgroup$
    – balazs.com
    Nov 16 '19 at 13:10
  • 1
    $\begingroup$ @balazs.com yes, two separate problems. $\endgroup$
    – JAGO
    Nov 16 '19 at 13:36
2
$\begingroup$

For the top problem

The graphs on the right side are 2-edge-connected, while those on the left can be disconnected with the removal of a single edge.

and for the bottom problem

The left side has only trivial automorphisms, while the right side all have at least one topological symmetry.

And in case my vocab didn't give me away, I am rather fond of graph theory. ^_^ Thinking of general audiences,

The bottom problem's 2C and 2F might be particularly prickly for someone more accustomed to thinking of symmetry geometrically than combinatorially.

Improve this answer
$\endgroup$
1
$\begingroup$

To the upper pair:

right side: each of the six contains a cycle that visits all of the vertexes without visiting an edge more than once, left side: none of the six contains a cycle that visits all of the vertexes without visiting an edge more than once

Improve this answer
$\endgroup$
9
  • $\begingroup$ What's the Eulerian cycle for $R(2,1)$? $\endgroup$
    – Alexander Geldhof
    Nov 16 '19 at 13:40
  • 1
    $\begingroup$ Okay, and why is L(1,1) a counterexample? $\endgroup$
    – balazs.com
    Nov 16 '19 at 13:52
  • 1
    $\begingroup$ I misread and misinterpreted your answer. Could you give the cycle for 2E? That's the only one I can't find. $\endgroup$
    – Alexander Geldhof
    Nov 16 '19 at 14:03
  • 1
    $\begingroup$ @AlexanderGeldhof imgur.com/9yS00Lq $\endgroup$
    – JAGO
    Nov 16 '19 at 14:09
  • 1
    $\begingroup$ imgur.com/RNBX7Lg this might be a clearer diagram of the cycle for 2E $\endgroup$
    – JAGO
    Nov 16 '19 at 14:15
0
$\begingroup$

Some observations on the first twelve graphs:

- All graphs are connected, i.e. there are no nodes to which have no associated edges
- All graphs are simple, i.e. two nodes have at most one edge between them, and nodes do not have edges to themselves
- All graphs on the left have at least one node of odd degree (where degree is the number of edges connecting to the node), while there are some graphs on the right which do not have a node of odd degree (graph R(1,1), i.e. the triangle, graph R(4,2) and graph R(4,1) )
- The maximal node degree on the left is $3$, while on the right it is $6$.
- Both right and left have graphs which admit a solution to the Konigsberg bridge problem, and graphs which do not admit such a solution.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.