Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.