I am working on this proof and sort of stuck on how to start:

Prove that if G is a connected graph with exactly 4 vertices of odd degree, there exist two trails in G such that each edge is in exactly one trail.

If anybody can give me some hints or help on how to start it! Thanks

  • $\begingroup$ we learned about euler path in class and if a graph has more than 2 odd degree vertices it can not have a euler path $\endgroup$ – Vera Feb 1 '18 at 22:08

Hint: Let your four odd-degree vertices be called $a,b,c,d$. Consider the multigraph formed by taking your original graph and adding an edge between $a$ and $b$ and an edge between $c$ and $d$.

What nice properties does this new multigraph have? How many vertices of odd degree exist in this multigraph? What does this imply? How can we use that to our advantage in regards to the original graph?

  • $\begingroup$ If I add connect ab and cd there's going to be 0 odd degree vertex so there is at least one euler circuit in the new graph, and then if I get rid of the two edge the circuit is now disconnect but there will be two separate kinda "trail" thing. Is this correct? $\endgroup$ – Vera Feb 1 '18 at 22:13
  • $\begingroup$ You could avoid invoking multigraphs by also adding a new vertex in the middle of each of the new connections. $\endgroup$ – Joffan Feb 1 '18 at 22:57

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.