I'm reading Hatcher's Algebraic Topology and I have a question regarding the proof of Proposition 1A.1. I will outline the proof here and highlight the part I don't understand.

Note: I'm sorry if this is a trivial question. I'm self-reading the book and have no other place to ask this.

Proposition 1A.1: Every connected graph contains a maximal tree.

Proof: Let X be a connected graph. Hatcher starts with an arbitrary subgraph $X_0\subset X.$ The idea is to embed $X_0$ as a deformation retract of a subgraph $Y\subset X$ that contains all vertices of $X$ i.e., a maximal tree.

First, the author constructs a sequence of subgraphs $X_0\subset X_1\subset X_2...$ by obtaining $X_{i+1}$ from $X_i$ by adjoining the closures $\bar{e_\alpha}$ of all edges $e_\alpha\subset X-X_i$ having at least one endpoint in $X_i.$ And then the author argues that the union $\bigcup_{i} X_i$ is both open and closed, and hence $X = \bigcup_{i} X_i,$ since $X$ is connected.

I understand everything so far. What I don't understand is the part of the following paragraph below that I have typed in bold letters.

"Now to construct $Y$ we begin by setting $Y_0 = X_0.$ Then inductively, assuming that $Y_i\subset X_i$ has been constructed as to contain all the vertices of $X_i,$ let $Y_{i+1}$ be obtained from $Y_i$ by adjoining one edge connecting each vertex of $X_{i+1}-X_i$ to $Y_i,$ and let $Y = \bigcup_i Y_i.$ It is evident that $Y_{i+1}$ deformation retracts to $Y_{i},$ and we may obtain a deformation retraction of $Y$ to $Y_0=X_0$ by performing the deformation retraction of $Y_{i+1}$ to $Y_{i}$ during the time interval $[1/2^{i+1},1/2^i].$"

I understand the remainder of the proof. Could someone please help me with this part?

Any help is truly appreciated. Thank you for your time.


1 Answer 1


A graph $G$ is a $1$-dimensional CW-complex. Its $0$-skeleton $G^0$ is nothing else than the set of vertices of $G$.

The $Y_i$ (plus auxiliary $V_i$) are constructed inductively as follows.

  1. Base case $i = 0$: Define $Y_0 = X_0$ and $V_0 = X_0$.

  2. Inductive step: Define $V_{i+1} = X^0_{i+1} - X^0_i$. For each $v \in V_{i+1}$ choose one edge $e(v)$ in $X$ which connects $v$ to a vertex $f_i(v) \in X^0_i$. The existence of such connecting edges follows from the construction of $X_{i+1}$.
    Then define $Y_{i+1} = Y_i \cup X^0_{i+1} \cup \bigcup_{v \in V_{i+1}} e(v)$.

Clearly $Y^0_i = X^0_i$, thus $Y = \bigcup_i Y_i$ contains all vertices of $X$.

We can regard the above assignment $v \mapsto f_i(v)$ as a map $f_i : V_{i+1} \to V_i$. Letting $j_i : V_i \to Y_i$ denote inclusion, we see that $Y_{i+1}$ is nothing else than the mapping cylinder $M(j_i \circ f_i) = (V_{i+1} \times [0,1] + Y_i)/(y,0) \sim f_i(y)$ of $j_i \circ f_i$, thus $Y_i$ is a strong deformation retract of $Y_{i+1}$.

That you do not understand

we may obtain a deformation retraction of $Y$ to $Y_0=X_0$ by performing the deformation retraction of $Y_{i+1}$ to $Y_{i}$ during the time interval $[1/2^{i+1},1/2^i]$

does not surprise me because Hatcher's sketch does not work. We can of course inductively construct strong deformation retractions from all $Y_i$ to $Y_0$, but in that way we never get a strong deformation retraction from $Y$ to $Y_0$. Look at the following simple example:

$X = [0,\infty)$ with vertices all integers $i \in \mathbb N_0$ and edges all open intervals $(i, i+1)$ with $i \in \mathbb N_0$. With $X_0 = \{0\}$ we get $X_i = Y_i = [0,i]$. Clearly $Y_{i+1} = [0,i+1]$ has $Y_i = [0,i]$ as a strong deformation retract, and succesively composing all deformations $D_{i+1}, D_i, \ldots , D_1$ we get a deformation from $Y_{i+1} = [0,i+1]$ to $Y_0 = \{0\}$. But this does not help us, because we can do only finitely many steps and never get a deformation from $[0,\infty)$ to $\{0\}$.

Thus we need a completely different approach. In the above example simply take $D : [0,\infty) \times [0,1] \to [0,\infty), H(x,t) = (1-t)x$.

Here all $x \in [0,\infty)$ are moved simultaneously along the ''downward'' paths connecting $x$ and $0$ until they reach $0$ at $t = 1$.

This also can be done in the above situation.

Even more generally, let $f_i : Z_{i+1} \to Z_i$ be a sequence of maps, $i \in \mathbb N_0$. The mapping telescope of this sequence is defined by $$T(\{ f_i\}) = \left( Z_0 \times \{0\} \cup \bigcup_{i = 1}^\infty Z_{i+1} \times [i,i+1] \right) / \sim$$ where $Z_{i+1} \times [i,i+1] \in (z,i) \sim (f_i(z),i) \in Z_i \times [i-1,i]$ (for $i = 0$ we replace $[i-1,i]$ by $\{0\}$). The mapping telescope can be regarded as the union of all mapping cylinders $M(f_i)$ of the maps $f_i$ where the top of $M(f_i)$ is identified with the base of $M(f_{i+1})$.

It is easy to verify that the above graph $Y$ is homeomorphic to the mapping telescope of the sequence of maps $f_i : V_{i+1} \to V_i$.

In exercise 1 on p.320 Hatcher denotes our mapping telescope as "reverse mapping telescope" and asks the reader to prove that $X_0 = X_0 \times \{0\}$ is a strong deformation retract of the mapping telescope.

I shall not prove it here, it is another question. The idea is the same as above: Simultaneously move all points $x$ along the (unique!) ''downward'' paths connecting $x$ and $0$ until they reach $0$ at $t = 1$. If you do this properly, you get a deformation from $Z$ to $Z_0$.


You must log in to answer this question.

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