The Gateway to Computer Science Excellence
+10 votes
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$.)
in Graph Theory by Veteran (105k points)
edited by | 338 views

1 Answer

+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.

by Boss (38.7k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
105,265 users