0
$\begingroup$

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?

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

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.

enter image description here

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