Finding two spanning graphs in a 4-regular connected graph

89 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.