Prove if $G=(E,V)$ is a 4-regular connected graph then $G$ has two spanning graph $G_1(E_1,V)$ and $G_2(E_2,V) $ such as:

$\mathbf 1.$ $\forall$ $v$ $\in$ $V$ in $G_1$ and $G_2$ $deg(v) = 2$ .

$\mathbf 2.$ $E_1 \cap E_2 = \varnothing$ .

$\mathbf 3.$ $E_1 \cup E_2 =E $ .

Each vertex in $G$ has an even degree and thus $G$ has an Euler's path in him. According to Euler's theorom if $G$ has a Euler's path then $G$ has a division of disjoint circles. Because they are disjoint cycles they follow requirements 1, 2 and 3 but I can't prove why this cycles will also be spanning graphs.

Suggestion and guidelines will be appreciated.

  • $\begingroup$ A cycle is where each vertex has degree two. So really, can you create two Hamiltonian circuits? Pick two edges per vertex and fix them. Can you traverse each vertex and end at your starting point? Now look at the two edges per vertex not originally chosen. $\endgroup$
    – ml0105
    Commented Apr 7, 2014 at 13:23

1 Answer 1


Find an Eulerian trail of $G$. Pick every other edge of the trail to construct $G_1$ and what is left is $G_2$. Since every vertex appears twice in the trail, $G_1$ and $G_2$ each contains exactly two edges incident with every vertex. Hence $G_1$ and $G_2$ satisfy the desired properties.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .