Hamiltonicity of $G^2$

I am going through a proof of hamiltonicity of $G^2$ and stuck quite in the beginning.

Some definitions:

$G$ is a finite non-hamiltonian 2-connected graph, $C$ is a cycle in $G$, $D$ is a component of $G-C$ and $C$-trail is either a $C$-path or a cycle meeting $C$ in exactly one vertex.

Square of a graph $G$ (denoted by $G^2$) is a graph in which two vertices are adjacent if and only if they have distance at most 2 in $G$. That means $G^2$ is "created" from $G$ by adding an edge connecting vertices whose distance is at most 2.

The part where I am stuck:

If $D$ consists of a single vertex $u$, we pick any $C$-trail in $G$ containing $u$, and let $E_D$ be the set of its two edges. If $|D| > 1$, let $\tilde{D}$ be the (2-connected) graph obtained from $G$ by contracting $G−D$ to a vertex $\tilde{x}$. Applying the induction hypothesis to $\tilde{D}$, we obtain a Hamilton cycle $\tilde{H}$ of $\tilde{D^2}$ whose edges at $\tilde{x}$ lie in $E(\tilde{D})$.

I really do not understand how $\tilde{H}$ is obtained, can you help me? What exactly is "the induction hypothesis"?

The statement is here, page 301, last lines of that page. Also here, page 2, with exactly the same wording.

At the beginning of the proof, they state they are performing induction on $|G|$. Presumably, this means the inductive hypothesis is

suppose the theorem is true for all graphs $G'$ such that $|G'| < |G|$

It looks like this proof is following a "divide and conquer" pattern I have sometimes seen in proofs involving graphs:

• Identify a subgraph D of G
• Solve a related problem on the "outside" of D
• Solve a related problem on D
• Piece those solutions together to get a solution to the problem we're actually interested in for G

And you frequently solve the subproblems by recursion -- i.e. you use the same approach to each subproblem, and eventually the subproblems become small enough that they are trivial, and you invoke the base case.

Typical meanings for "outside of D" are the graph where D is collapsed to a vertex, the graph where you remove all vertices (and incident edges) in D from G, or the graph where you remove all edges in D from G.

A likely relevant example is to construct a cycle on G, you can first first collapse a subgraph D to a single vertex to get G', construct a cycle C on G', then get a cycle on G by finding a path in D that connects the two vertices where C enters D.