How to show that every self-complementary graph is traceable (contains a Hamiltonian path)?


Self-complementary graph Hamiltonian-Path Traceable Graph

  • $\begingroup$ Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem? $\endgroup$ – Thomas Lesgourgues Jan 30 at 12:14
  • $\begingroup$ Your source for the definition of “traceable” links to a pdf of a thesis by Ferrugia which contains a proof of the result you want. Also note that not all self-complementary graphs have Hamilton cycles - $P_4$ for example. $\endgroup$ – Chris Godsil Jan 30 at 12:48

You can order the vertices of $G$ such that $$d_1 \leq \ldots \leq d_n$$

Now, because $G$ is self-complementary, you can check that its vertices verify ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):

$$ d_i \leq i-1 < \frac{n+1}{2} \Rightarrow d_{n+1-i} \geq n-i$$

Let $G'$ be a graph built from $G$, adding one vertex $u$, connected to all vertices of $G$. Then the vertices of $G'$ verify

$$ d_i \leq i < \frac{n}{2} \Rightarrow d_{n-i} \geq n-i$$ This is the condition for Chvatal's theorem, hence $G'$ contains a Hamiltonian circuit. Then by deleting $u$, G must contain a Hamiltonian path.

Edit See here, p164-165 for a proof of Chvatal's theorem. This is a proof by contraposition. The key point is to take $G$ as maximal non-hamiltonian, i.e. the addition of any edge would make $G$ hamiltonian. Therefore $G$ must include an hamiltonian path (remember that hamiltonian = cyle, minus an edge = path). And then working on some maximal degree vertices, you reach the above inequalities

  • $\begingroup$ Can you explain what is the Chvatal's theorem proof? Also, is there any alternate proof for this? $\endgroup$ – Ayush Chaurasia Jan 30 at 13:42
  • $\begingroup$ I edited the post, with a link to the proof $\endgroup$ – Thomas Lesgourgues Jan 30 at 15:12

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.