Suppose there is a $4$ regular graph. Then it has $2$ edge disjoint $2$-regular spanning subgraphs. Let the spanning subgraphs be $T_1$ and $T_2$. Can there be another pair $T_3$ and $T_4$ of edge disjoint $2$-regular spanning subgraphs for the same graph? I mean that can we regard the existance of two edge disjoint $2$-regular spanning subgraphs as a unique existance?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Take $K_5$, the complete graph on $5$ vertices. Any cycle containing every vertex (Hamiltonian cycle if you are familiar with the terminology) and its complement exactly act as you describe. This graph contains more than $2$ Hamiltonian cycles, so this decomposition is not unique. Explicitly, if we take the vertices to be $\{a,b,c,d,e\}$, the decomposition into cycles $a-b-c-d-e-a$ and $a-c-e-b-d-a$ is distinct from the decomposition into $a-b-d-e-c-a$ and $a-d-c-b-e-a$.
