Dirac's Theorem says:
If a connected graph $G$ has $n \ge 3$ vertices and $\delta(G) \ge \frac{n}{2}$, then $G$ is Hamiltonian.
Now I want to prove this theorem by induction on $n$.
For $i=3$, we have $\delta(G) \ge 2$ which means our graph is complete. So, it has a cycle with the length of $n-1+1=n$ which is a Hamiltonian cycle.
Now we assume that for every integer less than $n$, if we have a graph like $G$ with $\delta(G) \ge \frac{n}{2}$ , $G$ is hamiltonian.
What we want to prove is that a graph with $n$ vertices and $\delta(G) \ge \frac{n}{2} $ , is Hamiltonian.
Assume that $G$ is a graph with $n$ vertices. If $G$ is a complete graph, then it is Hamiltonian and we are done. So we should prove the theorem for the graphs which are not complete.
If $G$ is not complete, then we have:
$\exists u \in V(G)$ $\exists v \in V(G)$ $uv \notin E(G)$.
Now we define $G':= G-\{u,v\}$
in $G'$, we have 3 kinds of vertices : The vertices which have 2 or more adjacent vertices, the vertices which are not connected to any of the vertices and the vertices which are connected to just 1 vertex.
Now I'm stuck on this and i don't know how to use induction.
What should i do next?
Thanks in advance.
Best Answer
I think to use induction you should start simmilar to this:
Hypothesis: A graph with n-1 vertices and a minimum degree for each vertex of $(n-1)/2$ it is Hamiltonian.
Now take a graph with n vertices and look at one specific "added" vertex. You will notice that each of the other n-1 vertices has at most one edge conneced to the added vertex.
What does this tell you about the subgraph consisting of these $n-1$ vetices? What do you do with the "added" vertex, which has $n/2$ or more edges?
I hope this is enough of a hint how to start the induction. Your ansatz does not quite work since $\delta(G)$ is the minimum degree for each vertex so each vertex has at least n adjacent vertices.