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.

| cite | improve this answer | |
  • $\begingroup$ How does hamiltonicity follow from that? I fail to see the connection on size of $G$ and hamiltonicity of $\tilde{D}$. $\endgroup$ – Ohto Nordberg Feb 14 '13 at 13:02
  • $\begingroup$ The inductive hypothesis is that the theorem is true for $|G'| < |G|$. $|\tilde{D}| < |G|$ and (presumably) $\tilde{D}$ satisfies the hypotheses of the theorem. Therefore, the inductive hypothesis implies $\tilde{D}$ satisfies the conclusion of the theorem. $\endgroup$ – user14972 Feb 14 '13 at 17:23
  • $\begingroup$ @Hurkyl Here it is the other way around, you contract $G-D$ into a vertex $\tilde x$ apply the induction hypothesis to $\tilde{D}^2$ and extract from $\tilde H$ some $D \leadsto x$ edges ;-) $\endgroup$ – dtldarek Feb 15 '13 at 8:23
  • $\begingroup$ I still draw blank when trying to figure how hamiltonicity of $\tilde{D^2}$ comes about. I find no induction step here. I go in circle like "assume $\tilde{D^2}$ is hamiltonian, therefore $\tilde{D^2}$ is hamiltonian". Sorry guys, could you please dumb it down a little bit for me? $\endgroup$ – Ohto Nordberg Feb 15 '13 at 16:58
  • $\begingroup$ The argument is "$\tilde{D}$ is a 2-connected finite graph smaller than $G$. Therefore $\tilde{D}^2$ is Hamiltonian." $\endgroup$ – user14972 Feb 15 '13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.