1
$\begingroup$

Original question: $G$ is a simple undirected planar graph with 9 vertices. Suppose that every vertex in G has the same degree (regular). Prove or disprove that the complementary graph $\bar G$ must have a Hamiltonian cycle.

This is part of a past paper for a discrete math course, but the answers were not provided. I have tried to do it for a while now, but I don't even have any idea how to start this proof. Could someone please point me in the right direction, or even better, show me how to do this?

$\endgroup$
1
$\begingroup$

Planar graph on $n$ vertices has at most $3n - 6$ edges if $n \ge 3$ (this follows from Euler's formula). Since $G$ is regular graph on $9$ vertices we have $\deg G \le \lfloor \frac{2\cdot 21}{9}\rfloor = 4$. Then $\deg \overline{G} \ge 4$. If $\deg \overline{G} \ge 5$ then it is Hamiltonian by Dirac's theorem. The remaning case is $\deg \overline{G} = 4$.

Futher my solution becomes rather sophisticated in spite of OEIS tells that are at most 16 possible graphs $\overline{G}$ left to consider. So I just point that all of them are Hamiltonian.

$\endgroup$
  • $\begingroup$ it's *Dirac"... $\endgroup$ – Frank Apr 10 '17 at 9:54
  • $\begingroup$ Yes, you are right. $\endgroup$ – Smylic Apr 10 '17 at 12:57

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.