2
$\begingroup$

It is known that every $r$-regular graph on $2r+1$ vertices is Hamiltonian (Nash-Williams theorem, see here).

Now, I wonder if there is a simpler way to show that the graph on $4n+3$ ($n \ge 1$) vertices with degree sequence $(2n+1, \ldots, 2n+1, 2n+2)$ is Hamiltonian?

("a simpler way" means not to use the arguments in the proof of Nash-Williams theorem here).

For example, the graph with degree sequence $(3, 3, 3, 3, 3, 3, 4)$ must be Hamiltonian.

  • 0
    Actually we were wondering about the same question. Have you found such a result in literature? Nash-Williams arguments seem to work, but are there any published results with or without using this argument?2014-08-26

0 Answers 0