Every Halin Graph has a Hamilton Cycle Hi I want to proof that every Halin graph has a Hamilton cycle, my professor told me 
"use induction on the order of the graph $H=T\cup C$ where $T$ is the tree and $C$ its exterior cycle, the initial case being when $T$ is a star and $H$ a wheel. If $T$ is not a star, consider a vertex of $T$ all of whose neighbours but one are leaves"
But I can't see how to do it, can you give an orientation?
 A: (We use $G$ for the graph we are checking, this is different from the question).
We use induction on the number of nonleaf vertices, i.e. the number of vertices  "inside" $C$.
I will assume that you can do the induction base (the wheel) by yourself.
For the induction step let $P$ be a path of maximum length in $T$.
Because $T$ is not a star the length of $P$ is at least 3.
Let $v$ be an endpoint of $P$ and $w$ its neighbour.
Assume we have a standard planar embedding of $T\cup C$ and assume
the neighbours of $w$ on $C$, in clockwise order, are $v_1,\ldots,v_k$ (one of them is $v$).
Let $x$ be the vertex on $C$ before $v_1$ and $y$ the vertex on $C$ after $v_k$.
Note that $x\ne y$ (why?).
Because $P$ was a longest path $w$ has only one other neighbour.
Now remove $v_1,\ldots,v_k$ and add edges $wx$ and $wy$.
Let $C'$ be the new outer cycle.
We have created a Halin graph $G'$ with less "internal" vertices, so by the induction hypothesis
it has a Hamiltonian cycle $H$.
Because $w$ only has degree 3 in $G'$ at least one of the edges $wx,wy$ must be on $H$.
We may assume $wx$ is on $H$.
Now replace $wx$ by $wv_1\ldots v_kx$ and we have found a Hamiltonian cycle in $G$.
