# A question on the proof of Proposition 1A.1 of Hatcher's Algebraic Topology

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].$$"

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

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$$.