# Prove Dirac's Theorem by induction on the number of vertices

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?

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.

• i don't get it. please explain it more. – Arman Malekzadeh Apr 7 '16 at 8:38
• if you consider one of the vertices (of the graph with n vertices) the remaining graph (with n-1 vertices) fullfills the induction hypothesis. Note that the one every vertex in the remaining graph has at least degree n-1 (Why?). Do you understand this part of the induction? – Inflax Apr 7 '16 at 16:18
• I don't think this is going to work, because vertices which are connected to the special vertex now have degree $(n-2)/2$ , not $(n-1)/2$. – Andrea Marino Jul 9 at 12:13