I want to prove the following statement:
Suppose $G$ is a (simple) Hamiltonian graph with at least $4$ vertices. If $G$ is not a cycle, then it contains at least two vertices of degree $\geq 3$.
Intuitively this makes a lot of sense and I tried using induction on the number of vertices of the graph in order to get a result, but I got stuck and don't know how to proceed. If $G$ has $4$ vertices, then it is either $K_4$ or $K_4^-$ (by which I mean the complete graph on $4$ vertices, and the complete graph on $4$ vertices minus an edge, respectively). So in this case (the base case of the induction) it is obvious that $G$ contains at least two vertices of degree $3$.
How do I go on from there? Thanks in advance.
Best Answer
I don't think induction is your best approach, although people often achieve interesting and surprising results with methods I consider unpromising.
Here we know that there is a Hamiltonian circuit. Take one example of such and since $G$ is not a cycle graph there must be at least one other edge which connects two points but is not part of that cycle - giving the two end points of that edge degree of (at least) $3$.