I have a homework for my class to Combinatorics and Graphs which I'm not sure how to finish.

The task: Let G be a simple graph on 14 vertices, with 4 vertices having degree 5 and 10 vertices having degree 7. Prove that G is Hamiltonian.

We've went through Dirac's and Ore's theorems, but I'm not sure how to use them (at least at the start of the proof), and also Chvátal-Erdős theorem, which seems more appropriate to begin with.

Where did I come so far: We know that the number of edges in this graph is 45 (that is, 4*5 + 10*7 divided by two, as we count every edge twice through degrees), and the $K_1$$_4$ has 91 edges (($14,2$) - combination number), so we still could somehow add 91-45 = 46 edges. Now, from one variation of C-E theorem, I know that:

G is Hamiltonian $\iff G=(V,E_+)$ is Hamiltonian, where E+ is E plus edge between two not adjacent vertices whose sum of degrees is larger or equal to n. With knowing that I can add 46 edges, I can get to the point when I know that two 7-deg vertices are not connected - there's simple not enough vertices between them. So I can add an edge, and what I wanted to prove is that I can add the edges in a way that there will be then two at-least-9-deg vertex for each 5-deg vertex, and so I'd be able to connect them in a same way as I did with 7-deg vertices, up to the point when every 5-deg vertex would have degree of 7, after which point I could use Dirac's theorem to prove that G is Hamiltonian. However, this doesn't seem like the good way, or at least I'm not entirely convinced about it.

Could anybody please comment wether this is the good way to go, or better yet, point me in the right Dirac'tion for the proof? Thanks!!


Let $G'$ be the closure of $G$, so we know $G'$ has at least 10 vertices of degree $\geq7$. Suppose that $G'$ still has a vertex $v$ of degree $7$ or $8$. This vertex is non-adjacent to at least 5 other vertices, and only 4 of them can have degree $<7$. So $v$ is non-adjacent to a vertex $u$ of degree $\geq7$, but then $uv$ would be a "closure-edge", which contradicts the maximality of $G'$.

So we now know that $G'$ has at least 10 vertices of degree at least $9$ and at most 4 vertices of degree $5$ or $6$. Let $u$ be a vertex of degree $5$ or $6$. It is nonadjacent to at least 7 other vertices, so it must be nonadjacent to some vertex $v$ of degree at least 9. But then again $uv$ is a "closure-edge". Contradiction.

So there cannot be any vertex of degree $5$ or $6$ and we already excluded vertices of degree $7$ or $8$. So each vertex has degree at least $9$, so you can use Ore or Dirac to demonstrate a Hamiltonian cycle. (It is not hard to prove that $G'$ must be complete, but you don't need that).

| cite | improve this answer | |
  • $\begingroup$ thank you for your answer! When you say 'Suppose that $G'$ still has a vertex $v$ of degree $<9$', you take only vertex from the 10 vertices of degree $>=7$ as possibilities? $\endgroup$ – Gyfis Dec 4 '13 at 10:40
  • $\begingroup$ No, that was not my intention. I showed that the closure of $G$ cannot have any vertex of degree < 9, irrespective of the degree they had in $G$. The only thing I use of $G$ is that there are at most 4 vertices of degree < 7. $\endgroup$ – Leen Droogendijk Dec 4 '13 at 12:38
  • $\begingroup$ But how do you know that this vertex $v$ of degree $<9$, while definitely being non-adjacent to at least one vertex $u$ of degree $\geq7$, has degree large enough for $uv$ to be a "closure-edge", that is larger or equal then 7? Why can't $v$ have degree of 5 or 6? $\endgroup$ – Gyfis Dec 4 '13 at 13:16
  • $\begingroup$ You are right. I should have said: suppose that $G'$ still has a vertex of degree $7$ or $8$. I'll edit the answer to fix that. Is it sufficient for you to finish the proof, or do you need me to write down a full proof. $\endgroup$ – Leen Droogendijk Dec 4 '13 at 14:24
  • $\begingroup$ If it won't be a problem for you, I'd really appreciate a full proof. I have an idea of how to finish (using another contradiction), but still, I'm not that precise and I'm afraid it'll fail in some detail. Thanks! $\endgroup$ – Gyfis Dec 4 '13 at 14:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.