dirac's theorem not work
I am studing graph theory specifically hamiltonian cycles
I have a doubt with a exercise, it is a connected simple graph with 13 vertices, the book says that this graph has a hamilton cycle(truly it has)
each vertex has degree 2,3,4 or 5
By dirac's theorem this graph cannot have a hamilton cycle because $\delta$ (G) < $\frac{n}{2}$ where n = 13
does dirac's theorem work sometimes?
$\endgroup$ 21 Answer
$\begingroup$Dirac's theorem says that
IF you have $\delta(G)\geq \frac{n}{2}$ THEN the graph is hamiltonian.
$P\implies Q$ is not the same thing as $\neg P\implies \neg Q$.
Just because $\delta(G)<\frac{n}{2}$ it is not implied that the graph is not hamiltonian.
Take for trivial counterexample the graph $C_{100}$, the cycle of length 100. This graph is clearly hamiltonian since the graph itself is a hamiltonian cycle, yet the degree of every vertex is $2$ which is much less than $\frac{100}{2}=50$.
The information you have given us so far is not enough to confirm whether the graph does or does not have a hamiltonian cycle.
$\endgroup$ 2
