Determine if the graph is Hamiltonian using Dirac's theorem

Question

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?

Answer 1

Welcome to MSE!

Hint: How many edges are there in a complete graph on $15$ vertices? So how many edges have you removed? Even if you removed each of these from the same vertex, how many edges would it have? How does this compare to Dirac's condition?

---

I hope this helps ^_^

Answer 2

Let $G=(V,E)$ be such that $|V|=15$ and $|E|=99$.

To show that $G$ is Hamiltonian it suffices to show $\deg(v)\ge 8$ for all $v\in V$.

Suppose instead that $\deg(v)\le 7$ for some $v\in V$.

Then for the graph $H=G-v$, the sum of the degree is at least $$ 2{\,\cdot\,}99-2{\,\cdot\,7}=184 $$ contradiction, since $H$ has $14$ vertices, so the sum of the degrees is at most $14{\,\cdot\,}13=182$.