Prove this $2$-connected graph has a hamilton cycle

Question

I meet with this problem in my homework. It asks me to use a special trick to prove theorem 1 in the following essay.

New sufficient condition for cycles in graphs

The trick is : A simple undirected graph G is Hamiltonian if and only if its closure c(G) is Hamiltonian.

The definition of the closure of graphs can be seen here:Definition of the closure of undirected graphs

I would appreciate if anyone could help

Answer 1

Theorem 1 in the paper you're citing says

Let $G$ be a $2$-connected graph on $n\ge 3$ vertices. If, for every two distinct vertices $u,v$ of $G$, $$d(u,v) = 2 \implies \max \{\deg(u), \deg(v)\} \ge \frac n2$$ then $G$ contains a Hamiltonian cycle.

I have rephrased slightly to make the order of quantifiers more clear.

---

To get you started: let $A$ be the set of vertices of $G$ with degree at least $\frac n2$, and let $B$ be the set of all other vertices. Then:

• Each component of the induced graph $G[B]$ is a clique. (Why?)
• Each vertex of $A$ has edges to at most one of these clique components. (Why?)

In the closure of $G$, all edges between vertices in $A$ are added. To find a Hamiltonian cycle in the closure of $G$, proceed as follows:

1. Find vertex-disjoint paths with endpoints in $A$ that cover all of $B$.
2. Join them together using edges in $A$.

Conclude that $G$ also has a Hamiltonian cycle.