# Problem

(Fulton's Algebraic Topology: A First Course, Exercise 10.15) If $$X$$ is a finite graph with $$v$$ vertices and $$e$$ edges, and $$X$$ has $$k$$ connected components, show that $$H_1X$$ is a free abelian group with $$e-v+k$$ generators.

# Thoughts

First, WLOG, we could assume that $$k=1$$, i.e. $$X$$ is connected, and choose a spanning tree $$T$$ of $$X$$. Obviously, $$T$$ is contractible, therefore $$H_0T=\mathbb Z$$ and $$H_1T=0$$, and we're done when $$e=v-1$$. Now induction on $$e$$. Choose an edge $$K$$ of $$X$$ with the midpoint $$p$$. Let $$U=X\setminus\{p\}$$, and $$V=\operatorname{Int}K$$, the interior of $$K$$. The Mayer-Vietoris sequence for $$U,V$$ should be \begin{align*} 0&\to H_1(U\cap V)\to H_1(U)\oplus H_1(V)\to H_1(U\cup V)\\ &\to H_0(U\cap V)\to H_0(U)\oplus H_0(V)\to H_0(U\cup V)\to0 \end{align*} and we can (by induction) obtain that \begin{align*} &H_1(U\cap V)=0,H_0(U\cap V)\cong\mathbb Z^{\oplus 2}\\ &H_1(U)\cong H_1(X\setminus V)\cong\mathbb Z^{\oplus(e-v)},H_1(V)=0\\ &H_0(U)\oplus H_0(V)\cong\mathbb Z^{\oplus 2},H_0(U\cup V)=\mathbb Z \end{align*} However, I don't know how to make use of these information.

Any idea? Thanks!

Postscript: I don't know whether reduced homology could be used to conclude, but I prefer a proof without it since it's subsequently introduced in Problem 10.17.

• You haven't computed $H_1(U)$ and $H_1(V)$ yet. Commented Aug 24, 2014 at 12:32
• @LeeMosher Thanks. I've edited to include these. Commented Aug 24, 2014 at 12:46
• Sorry, could you please explain what you mean in the first part when you say "and we are done when $k=v-1$"?. And I am failing to see how we generalize this when we have $k$ connected components. Thanks
– user770533
Commented Dec 21, 2021 at 13:46
• @Cedric That was a typo. It should have been $e=v-1$ (with $k=1$), which is equivalent to the graph being a tree. Thanks for the question. Commented Dec 22, 2021 at 14:27
• No problem, it took me a while but eventually I understood it was typo haha. I would like to ask you some related question just in case. Do you how we can prove that the complement of the embedding of a graph in the plane has $e-v+k+1$ connected components?
– user770533
Commented Dec 22, 2021 at 14:42

$\newcommand{\Z}{\mathbb{Z}}$Here's a proof without reduced homology (which, by the way, makes the problem much simpler). To sum up what you've written (as far as I can tell it's correct), you're left with:

$$0 \to \underbrace{H_1(U) \oplus H_1(V)}_{\Z^{e-v}} \to H_1(X) \to \underbrace{H_0(U \cap V)}_{\Z^2} \xrightarrow{g} \underbrace{H_0(U) \oplus H_0(V)}_{\Z^2} \xrightarrow{f} \underbrace{H_0(X)}_{\Z} \to 0$$

$f$ sends $(a,b)$ to $a-b$ (because this is the MV sequence). The map $g$ sends both $(1,0)$ and $(0,1)$ to $(1,1)$ (easy examination). Finally you're left with an exact sequence:

$$0 \to \Z^{e-v} \to H_1(X) \to \Z \to 0$$ where the last $\Z$ is generated by $(1,-1)$ in $H_0(U \cap V) \simeq \Z^2$. By general facts about exact sequences (namely, $\Z$ is projective because it is free), you get $H_1(X) \simeq \Z^{e-v} \oplus \Z$.

• Could you explain a little bit more how you obtained the last isomorphism?
– user770533
Commented Dec 21, 2021 at 23:36
• @Cedric Let $P=\mathbb Z$. Every surjective morphism $p\colon M\to P$ of abelian groups admits a section $s\colon P\to M$ (i.e. $s$ is a morphism of abelian groups and $p\circ s=\operatorname{id}$). Then it is direct to show that $(\ker p)\oplus P\to M,(x,y)\mapsto x+s(y)$ is an isomorphism. The last comment about projectivity is that this holds for all $P$ being projective $\mathbb Z$-modules, not just for $P=\mathbb Z$. Commented Dec 22, 2021 at 14:32

We consider the case with only one connected component, like what you've said. We choose the spanning tree $T$ and done with $e=v-1$. We use Mayer-Vietoris in reduced homology, that is, \begin{align*} 0&\to H_1(U\cap V)\to H_1(U)\oplus H_1(V)\to H_1(X)\\ &\to \tilde{H}_0(U\cap V)\to \tilde{H}_0(U)\oplus \tilde{H}_0(V)\to \tilde{H}_0(X)\to0 \end{align*} Since $X,U,V$ are connected, thus $0$, but $U\cap V$ has two connected component, thus $\tilde{H}_0(U\cap V)=\mathbb{Z}$. So we have $$0\to H_1(U) \to H_1(X)\to \mathbb{Z}\to 0$$ as a short exact sequence. Then we use the result here to prove induction hypothesis.