information:filtering
Graphs

The fundamental group can be defined for discrete structures too. In particular, consider a connected graph G = (V, E), with a designated vertex v in V. The loops in G are the cycles that start and end at v. Let T be a spanning tree of G. Every simple loop in G contains exactly one edge in E \ T; every loop in G is a concatenation of such simple loops. Therefore, the fundamental group of a graph is a free group, in which the number of generators is exactly the number of edges in E \ T. This number equals | E | − | V | + 1.

For example, suppose G has 16 vertices arranged in 4 rows of 4 vertices each, with edges connecting vertices that are adjacent horizontally or vertically. Then G has 24 edges overall, and the number of edges in each spanning tree is 16 − 1 = 15, so the fundamental group of G is the free group with 9 generators. Note that G has 9 "holes", similarly to a bouquet of 9 circles, which has the same fundamental group.