= Solution
{c}
Choose a <spanning tree> $T$ of the finite <connected graph> $X$. It contains every <vertex> of $X$ and has $v(X)-1$ <edges> by part (i). Collapsing $T$ to a point is a <homotopy equivalence>: $T$ is a <contractible> <subcomplex>, and <collapsing a contractible cofibration> in a <CW complex> preserves <homotopy type>.
Every <edge> outside $T$ then becomes a <circle> attached to the common point. Hence the <quotient space> $X/T$ is a <bouquet of circles> with
$$
r=e(X)-e(T)=e(X)-v(X)+1
$$
petals. The <fundamental group of a bouquet of circles> is the <free group> with one member of a <free basis of a group> for each petal. Therefore the <rank of the fundamental group of a finite connected graph> is
$$
\boxed{\pi_1(X)\cong F_{\,1-\chi(X)},\qquad r=1-\chi(X).}
$$
More concretely, choose a <vertex> as <base point>; follow the unique <path in a graph> in $T$ to one end of a non-tree <edge>, traverse it, and return through $T$. These <based loops> give the <free basis of a group>. Thus $r$ is the number of free <group generators>, equivalently the minimum size of a <generating set of a group>, rather than the size of every possible redundant <generating set of a group>. Minimality also follows by <abelianization>, since $F_r$ has <abelianization> $\mathbb Z^r$.
Back to article page
