Homology of a finite graph follows from Mayer-Vietoris sequence? 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.
 A: $\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$.
A: 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.
