CMI2012-B-01

Question

Let $G=(V, E)$ be a graph where $\mid V \mid  =n$ and the degree of each vertex is strictly greater than $\frac{n}{2}$. Prove that $G$ has a Hamiltonian path. (Hint: Consider a path of maximum length in $G$.)

Answer 1

The proof is similar to Dirac theorem In an $n$-vertex graph in which each vertex has degree at least $\frac {n}{2}$ must have a Hamiltonian cycle.

So, we can say that If a graph contain Hamiltonian cycle, it will surely contain a Hamiltonian Path.

But the converse of this is not true.

Here, consider a graph with $4$ vertices and $6$ edges which is $K4$ and the degree of each vertex is $3$ $\left(\text{i.e} > \frac{n}{2}\right).$

 

So, the graph contains $a \ b \ c \ d$ one path.

$b \ c \ d \ a$  is another and even more paths exist.

And it even contains a Hamiltonian cycle.

Comments

Is this a proof ? You have just shown a particular case of Dirac theorem , which of course would always be true..

 

I feel this question is something like similar to asking verify if Rolle’s or Lagrange Mean value theorem is applicable