Every self-complementary graph contains a Hamiltonian path.

Question

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

Definitions:

Self-complementary graph Hamiltonian-Path Traceable Graph

Answer 1

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 the following implication ($d_i$ correspondant to $d_{n+1-i}$ in its complementary):

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

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