An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

3.1k Views Asked by At

Research effort:

$\rightarrow)$ I think this is relatively easy.

$\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can construct a simple edge-disjoint cycle.

Now let's call this set of edges $S$.

Let $G' = (V,E/S)$

It's easy to see that given that I deleted a pair number of edges for each vertex (or none, in case the vertex was not part of the cycle), and every vertex in $G$ had a pair number of vertex, then, all the vertex in $G'$ have even degree or degree $0$.

Let $w'$ be a vertex in $G'$ whit degree more than $0$. I can construct another simple edge-disjoint cycle...

I can keep doing this procedure until all the vertex in the graph have degree $0$. And at this point I'll have decomposed $G$ into simple edge-disjoint cycles, then QED.

This proof is horrible, I can see some errors whit the reasoning, such when I say: "I'm assured that I can construct a simple edge-disjoint cycle".

Can you help me whit a more sound proof?

1

There are 1 best solutions below

2
On

I think this proof works. You are missing proper formulation of your ideas into proof. I will be using strong induction to prove that every even graph decomposes into cycles.

Lemma 1. : If every vertex of a graph G has degree at least 2, then G contains a cycle. (Hint : consider maximal path in G).

Proof : We apply induction on number of edges. For e = 3, triangle is the even graph, and it is the cycle itself. Let, this be true for all graphs having number of edges less than e, for some e > 3. Using Lemma 1. this even graph G contains a cycle C. Consider the graph G' = G - E(C). G' is also an even graph, as the cycle has 0 or 2 edges at each vertex, so degree of each vertex remains even after removing edges of the cycle C. Now, G' is an even graph having lesser number of edges, so by principle of using induction it can be decomposed into cycles. The graph G now has the decomposition of G' and the cycle C. Hence proved.

QED. Hope this clarifies your argument.