340 views
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$.)

edited | 340 views

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.

by Boss (38.7k points)
edited