# Almost regular graphs that are Hamiltonian

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.

-
I do not know if there exist such result after the Nash-Williams theorem, but we can conclude the following corollary: Suppose $G$ is a graph on $n$ vertices with degree of each vertex is either $\left\lfloor \frac{n}{2}\right\rfloor$ or $\left\lceil\frac{n}{2}\right\rceil$. Then $G$ is Hamiltonian. – pipi Oct 24 '12 at 4:30
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? – user171743 Aug 26 '14 at 10:07