edited by
957 views

1 Answer

6 votes
6 votes

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.

edited by

Related questions

4 votes
4 votes
2 answers
1
go_editor asked May 22, 2016
834 views
Let $T$ be a tree on 100 vertices. Let $n_i$ be the number of vertices in $T$ which have exactly $i$ neighbors. Let $s= \Sigma_{i=1}^{100} i . n_i$ Which of the following...
19 votes
19 votes
3 answers
2