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$ 2More in general
"Zoraya ter Beek, age 29, just died by assisted suicide in the Netherlands. She was physically healthy, but psychologically depressed. It's an abomination that an entire society would actively facilitate, even encourage, someone ending their own life because they had no hope. Th…"
