# Every self-complementary graph contains a Hamiltonian path.

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

Definitions:

• Hi, could you give us some context? What do you know in graph theory? what have you tried to solve the problem? – Thomas Lesgourgues Jan 30 at 12:14
• 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. – Chris Godsil Jan 30 at 12:48

## 1 Answer

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

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