# Prove that these statements are equivalence for a connected graph

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?

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

## 1 Answer

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.