Vtyjkyuk

Dirac's Theorem says:

If a connected graph $G$ has $n ge 3$ vertices and $delta(G) ge fracn2$, 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 fracn2$ , $G$ is hamiltonian.

What we want to prove is that a graph with $n$ vertices and $delta(G) ge fracn2 $ , 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.

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.