A graph is a space built from a set of vertices by attaching edges, each a copy of [0, 1] whose two ends are glued to vertices. A tree is a connected graph that contains no circuit, and every tree is contractible. Every connected graph contains a maximal tree, and a maximal tree contains all the vertices [1].
Collapsing a contractible subgraph to a point is a homotopy equivalence. If T is a maximal tree in a connected graph X, the quotient X/T has a single vertex, and each edge outside T becomes a circle through it. So X is homotopy equivalent to a wedge of circles, one for each edge not in T, and \pi_1(X) is a free group with one generator for each such edge [1].
The generators can be read in X itself: for an edge e outside T, go from the base vertex to the start of e inside T, cross e, and return to the base vertex inside T. A maximal tree of a finite connected graph with V vertices and E edges has V - 1 edges, so the rank of \pi_1(X) is E - V + 1 = 1 - \chi(X), where \chi(X) = V - E is the Euler characteristic.
The figure eight has one vertex and two edges, and its fundamental group F_2 has rank 2 - 1 + 1 = 2. The complete graph K_4 has 4 vertices and 6 edges, so \pi_1(K_4) \cong F_3. In general the complete graph K_n on n vertices has n(n - 1)/2 edges, and its fundamental group has rank (n - 1)(n - 2)/2.
In the figure, K_4 is drawn as a triangle with a vertex in the middle, and the three edges from the middle form a maximal tree. As the tree shrinks to the middle point, the three sides of the triangle bend into three loops, and K_4 turns into the wedge of three circles. The three sides give the three free generators.
A covering space of a graph is again a graph. If p \colon \tilde{X} \to X is a covering map and X is a graph, take the preimages of the vertices of X as the vertices of \tilde{X}. Each open edge of X is simply connected, so its preimage is a disjoint union of copies of it, one in each sheet, and these copies are the edges of \tilde{X} [1].
Let F_n be the free group of rank n, viewed as the fundamental group of the wedge X_n of n circles, and let H \subset F_n be any subgroup. By the Galois correspondence there is a connected covering p \colon \tilde{X} \to X_n with p_*\pi_1(\tilde{X}) = H, and \tilde{X} is a graph. Since p_* is injective, H \cong \pi_1(\tilde{X}) is free. This is the Nielsen-Schreier theorem: every subgroup of a free group is free [1].
If H has finite index k, the covering graph has k sheets, hence k vertices and kn edges, because each vertex and each edge of X_n has k lifts. So the rank of H is kn - k + 1 = 1 + k(n - 1). In terms of Euler characteristics, \chi(\tilde{X}) = k\chi(X_n), and for n \geq 2 the rank grows with the index.
For example, H = \langle a^2, b, aba^{-1} \rangle \subset F_2 consists of the words in which a appears an even number of times, counted with signs. It has index 2, so it is free of rank 3, and a^2, b, aba^{-1} form a free basis. A subgroup can thus need more generators than the whole group, and F_2 contains free subgroups of every finite rank. For n = 1 the formula gives rank 1 for every k, matching the subgroups k\mathbb{Z} of \mathbb{Z}.
The figure finds the covering graph of H from its generators. It starts from three loops at the base vertex that spell a^2, b and aba^{-1} with labeled, directed edges, and folds together two edges with the same label that leave the same vertex. After two folds, every vertex has one incoming and one outgoing edge of each label, so the graph covers the figure eight with 2 vertices and 4 edges [2].
Folding does not change the subgroup that the graph represents, and when the folded graph is a covering, the number of its vertices is the index [2]. If the folded graph is finite but some vertex lacks an edge of some label, the subgroup has infinite index, so folding decides whether a finitely generated subgroup has finite index and computes the index.
Subgroups of infinite index can have infinite rank. The commutator subgroup [F_2, F_2] is the kernel of the homomorphism F_2 \to \mathbb{Z}^2 sending a and b to the two standard generators. Its covering graph is the grid in the plane, with vertices at the points of \mathbb{Z}^2, horizontal edges for a and vertical edges for b, and a loop lifts to a closed path exactly when its exponents of a and of b each add up to zero.
The grid is an infinite graph, and every maximal tree misses infinitely many of its edges, so [F_2, F_2] is free of infinite rank. In the figure, the commutator [a^m, b^n] = a^m b^n a^{-m} b^{-n} lifts to the boundary of the rectangle with corners (0, 0) and (m, n). The commutators [a^m, b^n] with m, n \neq 0 form a free basis of [F_2, F_2].
So a finitely generated group can have subgroups that are not finitely generated. By the formula of the previous section this does not happen for subgroups of finite index in F_n, and more generally every subgroup of finite index in a finitely generated group is finitely generated.
Another example is the kernel of the homomorphism F_2 \to \mathbb{Z} sending a to 1 and b to 0. Its covering graph is a line of a-edges through the integers with a b-loop at each integer. The line is a maximal tree, the loops are the remaining edges, and the kernel is freely generated by the conjugates a^k b a^{-k} with k \in \mathbb{Z}.
A similar argument with covering spaces of a wedge of two spaces gives the Kurosh subgroup theorem: every subgroup of a free product G_1 * G_2 is itself a free product of a free group and of conjugates of subgroups of G_1 and G_2. For G_1 = G_2 = \mathbb{Z}, all these factors are free, and the theorem reduces to the Nielsen-Schreier theorem for F_2.