# prove that the graph $G$ is hamiltonian

Problem: If $$G$$ is a graph with $$m$$ edges and $$n\geq 3$$ vertices, where $$2m \geq n^{2} - 3n + 6$$, prove that $$G$$ is a hamiltonian graph.

(Hint: Consider the following theorem and corollary.)

Theorem: Let $$G$$ be a graph. Then $$G$$ is a hamiltonian graph if and only if its closure, denoted $$\overline{G}$$, is a hamiltonian graph.

Corollary: Let $$G$$ be a graph on $$n \geq 3$$ vertices. If the closure of $$G$$ is complete, then $$G$$ is hamiltonian.

Thoughts: Honestly, I'm stuck. The hint isn't very useful to me, and I'm not able to immediately pull out any ideas. If you could guide me on how to get started, that would be helpful and appreciated.

In $$\overline G$$, the inequality $$n^2-3n+6\le 2m$$ still holds (with possibly increased $$m$$). This means $$m\ge {n\choose 2}-(n-3).$$ Let $$u,v$$ be two vertices in $$\overline G$$. Then the graph lacks at least $$(n-1-\rho(u))+(n-1-\rho(v))-1=2n-3-(\rho(u)+\rho(v))$$ edges (the edges missing per vertex minus possibly double-counted $$uv$$). This must be $$\le n-3$$. It follows that $$\rho(u)+\rho(v)\ge n$$, i.e., $$uv$$ is an edge in $$\overline G$$.
• What are $\rho(v)$ and $\rho(u)$? And how does your conclusion verify that $G$ is hamiltonian? Dec 19 '19 at 7:24
• @mathmajor $\rho(v)$ is the degree of vertex $v$ in $\overline{G}$. The conclusion implies that the closure of $G$ is complete hence $G$ is Hamiltonian by the corollary.
• @RyanGreyling Also, where did the $(n - 1 - \rho(u)) + (n - 1 - \rho(v)) - 1 = 2n - 3 - (\rho(u) + \rho(v))$ come from? How was this equation produced? Dec 19 '19 at 19:00
• Let $H$ be the graph complement of $G$. Let $h$ be the number of edges of $H$. A vertex can connect to at most $n-1$ vertices so the vertex $u$ in $H$ has degree $n-1-\rho(u)$. The same applies to $v$. We also subtract a $1$ just in case $u$ and $v$ are connected and we double count this edge. The whole point of the equation is to just get a nice lower bound for $h$. We already know that $h\leq n-3$. This way we can compare $2n-3-(\rho(u)+\rho(v))\leq n-3$.