Hamiltonian path in a complement of a tree

Question

T is a tree on n-vertices for which the greatest degree is smaller than n-1, prove that the complement of T has a Hamiltonian path.

I was trying to achieve Ore's inequality, this is what I have written so far:

Answer 1

Actually you can use induction. I'll give you partial solution, but it is not hard to fill the blanks.

Check for $n=4$ (convince yourself that the other cases can't happen).

Let us look at some leaf. If its parent has degree $\leq n-2$ then by removing this leaf we still have max degree $< n-2$ , but now we have tree on $n-1$ vertices , apply induction hypothesis to get a hamiltonian cycle C. You can get hamiltonian cycle for the original graph by connecting the removed vertex to 2 vertices that follow each other on the cycle(convince yourself).

Elseways, since the maximum degree $< n-1$ we get $\Delta = n-2$, meaning that we have a vertex with $n-3$ leaves , and one neighbour of degree 2. Now try to convince yourself (by drawing) that this graph's complement also contains hamiltonian cycle.

Answer 2

I think the easiest way to solve it is to remember the fact that any tree can be represented by bipartite graph .

So we get $T = G(A\cup B,E)$ now from the info about the max degree of $T$ we know that $\min\{|A|,|B|\} \ge 2$ .

Now just take the compliment of the bipartite graph and you can get a Hamilton path by starting at any of the sides and passing all the vertices at any order you want then switching to the other side and passing all the vertices of this side at any order.

$\Delta (T) < n-1$ means the compliment of $T = G(A\cup B,E)$ will be a connected graph. So it doesn't matter what vertex of $A$ or $B$ you arrive last it will allays have an edge to the other side .

And if we take any of the sides by itself it will be clique of the size of $|A|$ or $|B|$ since there were no edges between nodes of the same side in a original bipartite graph. So we can take the vertices in any order .