2
$\begingroup$

Theorem: Every regular graph of positive even degree has a spanning 2-regular subgraph.

This was taken from Corollary 5.10 of ETH Zurich's notes on graph theory. The proof constructs a Eulerian tour, splits the vertices into in and out vertices on the tour, then invokes Hall's theorem on the regular (and now bipartite graph) to get a perfect matching. This is joined together to form the spanning 2-regular subgraph.

While the proof seems relatively straightforward, I have two questions:

First, where is the 2-regular, spanning subgraph in this 4-regular graph? It seems to me that following the theorem it should have one, but I have been unable to identify a 2-regular, spanning subgraph in this relatively simple graph.

Second, doesn't this imply that every even degree, connected, regular graph has a Hamiltonian cycle?

$\endgroup$

1 Answer 1

2
$\begingroup$

A $2$-regular graph is a union of disjoint cycles.(So it doesn't have to be exactly one cycle)

You yourself have provided an example of a $4$-regular graph with a $2$-regular spanning subgraph but no hamiltonian cycle.

An example of a $2$-regular subgraph in your linked graph is the union of the following two cycles:

$(1,9,0,6,8,4,1)$ and $(2,10,3,5,7,2)$

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.