1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ What are $\rho(v)$ and $\rho(u)$? And how does your conclusion verify that $G$ is hamiltonian? $\endgroup$
    – mathmajor
    Dec 19, 2019 at 7:24
  • $\begingroup$ @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. $\endgroup$
    – Ryan
    Dec 19, 2019 at 17:42
  • $\begingroup$ @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? $\endgroup$
    – mathmajor
    Dec 19, 2019 at 19:00
  • $\begingroup$ 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$. $\endgroup$
    – Ryan
    Dec 19, 2019 at 21:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .