Question regarding the connectedness of spanning 2-regular subgraphs

132 Views Asked by At

If a 4-regular connected graph does not have one or more cut vertices then we can say it has a 2-regular spanning sub graph which is connected, isn't it? (A spanning sub graph with one component)

There might be several 2-regular spanning subgraphs, some which are a union of disjoint cycles, but if there is no cut vertex above type of a spanning sub graph will also be present, right?

Can someone please guide me to understand this.

Thanks a lot in advance. enter image description here

2

There are 2 best solutions below

2
On

Is this a good hint? If the graph $G $ is connected then because all degree of the vertices are even, $G $ has an eulérienne cycle. If $G $ is not connected, then each component of $G $ has an eulérienne cycle.

11
On

A "2-regular spanning subgraph which is connected" is simply a Hamiltonian cycle, and in general when you have a reasonable-sounding condition for a Hamiltonian cycle to exist, it's probably not good enough.

This MathOverflow answer gives one counter-example. (Here, a Hamiltonian cycle does not exist, because to visit every vertex, we would have to use the left and right vertices multiple times.)

The Meredith graph is an even stronger counter-example: it is not just $2$-connected but $4$-connected (the best we can hope for a $4$-regular graph) yet is not Hamiltonian.