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.


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.

  • $\begingroup$ i don't get it. please explain it more. $\endgroup$ – Arman Malekzadeh Apr 7 '16 at 8:38
  • $\begingroup$ 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? $\endgroup$ – Inflax Apr 7 '16 at 16:18
  • $\begingroup$ 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$. $\endgroup$ – Andrea Marino Jul 9 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.