1
$\begingroup$

Prove that these 3 statements are equivalence for a connected graph:

a. degree of all vertices are even

b. graph has a closed Euler path (An Euler circuit that can contain repeated vertices)

c. You can part graph edges into separate circuits in a way that each edge is in exactly 1 circuit.

Any hints how to prove?

$\endgroup$
  • $\begingroup$ I would prove $(a)\Rightarrow (b)\Rightarrow (c)\Rightarrow (a)$. $\endgroup$ – Henning Makholm Mar 7 '17 at 19:53
1
$\begingroup$

I think I would prove $(a)\Rightarrow(c)$ by induction on the number of edges, making one circuit $C$ and then observe that the conditions still hold for $G - E( C)$. Note that this would be a proof that doesn't rely on $G$ being connected.

Then moving on to $(c)\Rightarrow(b)$; given a set of circuits that contain all the edges of a connected graph, show that you can assemble these to make an Eulerian path.

Then finally $(b)\Rightarrow(a)$, given an Eulerian path show that all degrees are even.

$\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.