The Fundamental Groups of Connected Graphs

The Fundamental Groups of Connected Graphs

A graph $X$ consists of a set of vertices and a set of edges where each edge is associated with two vertices. The set of vertices is often denoted $V(X)$ and the set of edges is often denoted $E(X)$. We will only consider finite graphs that are connected - that is, the graph is one piece.

Computing the fundamental group of such graphs is relatively easy. We must first make some definitions first though.

 Definition: Let $X$ be a connected graph. A Tree in $X$ is a subgraph $T$ of $X$ that contains no loops, i.e., $T$ is simply connected. A Maximal Tree in $X$ is a subgraph $T$ of $X$ such that if $T'$ is another tree containing $T$ then $T' = T$.

For example, consider the following graph: Below are two examples of maximal trees in the graph above:  Theorem 1: Let $X$ be a path connected graph and let $T$ be a maximal tree in $X$. Then $\pi_1(X, x)$ is isomorphic to the free group generated by $|E(X)| - |E(T)|$ elements.

In the example above, the $3 \times 3$ grid $X$ has $E(X) = 24$ edges, and $E(T) = 15$ edges. So the fundamental group of $X$, $\pi_1(X)$ is $F_9$, the free group generated by $9$ elements.