How do I figure this out using Dirac's theorem?

105 Views Asked by At

I know that Dirac's theorem states “If $G$ is a graph with $n$ vertices, $n \geq 3$, each of degree at least $n/2$, then $G$ is Hamiltonian”, but how do I use this to prove that a graph with $99$ edges on $15$ vertices is Hamiltonian? Should I use a degree sum formula and compare that to the results of Dirac's theorem?

1

There are 1 best solutions below

0
On

Theorem: Graph with $n$ vertices and ${n-1\choose 2}+ 1$ edges has Hamilton cycle.

Proof: https://math.stackexchange.com/a/3469739/463553

Since $n= 15$ and $\varepsilon =99>92={14\choose 2} +1$ we are done.