11
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
5
+50
$\begingroup$

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.

$\endgroup$
10
  • $\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
    Commented Feb 14, 2013 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
    Commented Feb 14, 2013 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
    Commented Feb 15, 2013 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
    Commented Feb 15, 2013 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
    Commented Feb 15, 2013 at 17:14

You must log in to answer this question.

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