A 2-connected graph contains a path passing through all the odd degree vertices

461 Views Asked by At

I am trying to prove the above as an exercise in the topic of connectivity. I have tried to do so using ear decompositions, as odd degree vertices may be characterized as end points of ears, but to no avail. Any recommendations are appreciated. Thanks

1

There are 1 best solutions below

4
On BEST ANSWER

The statement is false. Take the following $5$-regular graph (inspired by the graph in this MathOverflow answer, which being $4$-regular didn't quite do the trick):

enter image description here

In this graph, every degree is odd, so we are looking for a Hamiltonian path. However, to visit each of the five parts around the sides, we would have to go through the middle vertices multiple times, so this is impossible.

For a slightly more formal argument: if a graph $G$ has a Hamiltonian path, it has a path $P_n$ as a subgraph. Deleting two vertices from $P_n$ leaves at most $3$ components, so the same must be true of $G$ (which is $P_n$ with extra edges). But in the graph above, deleting the two middle vertices leaves $5$ components, so it can't have a Hamiltonian path.