A Graph G where each vertex has an even degree can be split into cycles by which no cycle has a common edge.

1.8k Views Asked by At

According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ?

Here is the link in which it was proved, but i couldn't understand for the above scenario

http://mathonline.wikidot.com/euler-s-theorem (lemma-2 in this link)

2

There are 2 best solutions below

0
On

The lemma you mention does not state that it can be split into two cycles, just that it can be split into cycles. By convention this includes the case where it can be split into one single cycle. Your example is one single cycle.

0
On

Let $G$ be a graph where every vertex has even degree. Then it can be shown that $E(G)$ can be partitioned into cycles by using induction on $|E(G)|$.

This is the crux of the proof: Let us assume that $G$ has at least one edge, otherwise we are done. If every vertex in $G$ has even degree than there are no vertices of degree 1, which implies that if $G$ has at least one edge, then $G$ is not a forest [make sure you see why, that each connected component of $G$ w at least one edge is not a tree], which implies that $G$ has at least one cycle. Let $C$ be a cycle. Then if the graph $G' = G \setminus E(C)$ has no edges, then we are done. Otherwise, $G'$ also has all vertices of even degree [make sure you see why], so by the induction hypothesis, $E(G')$ can be partitioned into cycles $C_0,\ldots, C_{m}$. But then $C, C_0, \ldots, C_m$ is a partitioning of $E(G)$ into cycles.