# if G does not have vertices of odd degree, then there are disjoints cycles by edges

Show that if G does not have vertices of odd degree, then there are disjoints cycles by edges $$C_{1}, C_{2}, C_{3},...C_{m}$$ such that

$$E(G)=E(C_{1}) \cup E(C_{2})\cup ...\cup...\cup E(C_{M})$$

I think this problem is solved by Hamiltonian graphics, but I can't show it Can anybody help me?

• Thinking in terms of Eulerian cycles may be more helpful. – PJK Oct 23 '18 at 2:20

## 1 Answer

Let $$G$$ be a graph, If $$G$$ does not have vertices of odd degree, then $$G$$ cannot be a tree and hence contains a cycle. Now we prove by induction of $$|E(G)|$$ than $$E(G)$$ can decomposed as disjoint union of circles.

Base case: $$|E(G)|=2$$ is trivial to check. Now, Take a connected component $$Co_1$$ of $$G$$, $$Co_1$$ has a circle $$C_1$$ by previous reasoning. Now, $$G-|E(C_1)|$$'s edges can be decomposed as disjoint union of circles $$C_2,...C_n$$ by induction hypothesis, Well those circles together with $$C_1$$ form a disjoint union of circles for $$E(G)$$. Done.

Here is the proof from some notes. 