Algorithm for computing the rank of the fundamental group of a graph?

I've been learning a bit about applications of algebraic topology to graph theory and I'm interested in figuring out how to compute the fundamental group $\pi_1(X,x_0)$ of an arbitrary graph $G=(V,E)$. It seems to me you could use a simple DFS to compute the number of distinct cycles with any arbitrary $x_0$ as the base point. That would give you the number of generators in $\pi_1(X,x_0)$ and you'd know it's just the free group over those generators. Am I off base? If not, is that the most computationally efficient way to go about it? I'm pretty sure I can't (in general) use any simple formula like the Euler chracteristic...

• You can argue, for each connected component K of the graph G, that you can find a spanning tree for K, then the edges of G-T generate the fundamental group; each loop based at p will pass thru an edge in G-T; conversely, for every edge in G-T, you define a unique loop.
– gary
Sep 12, 2011 at 0:36
• Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help! Sep 12, 2011 at 14:48
• I'm not a programmer, but let me think things thru more carefully and see what I can come up with; the proof of the existence of the tree is constructive, so it would not be too hard to turn it into an algorithm .
– gary
Sep 12, 2011 at 16:20
• thanks gary. do you have a link to the proof? Sep 12, 2011 at 17:47
• No problem; here is the proof; I posted this question to some other site: at.yorku.ca/cgi-bin/… . You may also want to look into the Schreier Subgroup Lemma, which allows you to find the stabilizer of an element under a group action; an element of the stabilizer of some g in the graph G can be seen as a loop based at g. The Schreier subgroup lemma is an application of Reidemeister-Schreier to finding a generating set for a subgroup H og a group G using a transversal T for the quotient group G/H.
– gary
Sep 12, 2011 at 18:05

1 Answer

In case anyone else wants to know the answer, I figured it out. The fundamental group $\pi_1(X)$ of a graph $X=(V,E)$ is the free group on $k$ generators, $k = 1 - |V| + |E|$,. This is given by $1 - \chi$, where $\chi$ is the usual Euler characteristic, $V-E$.

• Correct: if $T$ is a spanning tree of the graph, then $\pi_1(X)$ is freely generated "by" the vertices in $X$ that are not in $T$. But you don't need to find the maximal spanning tree, you just need to count how edges it has. Since a connected tree with $n$ vertices has $n-1$ edges, the formula follows. Sep 16, 2011 at 20:28
• @Arturo I think you meant "edges" in the first line. :) Sep 16, 2011 at 21:21
• @Srivatsan: Oops; quite so. Too bad I can't edit it anymore... Sep 17, 2011 at 4:20
• To be clear, this is correct for connected graphs. For possibly disconnected graphs, you need to count just the vertices and edges in the component of the basepoint. Dec 22, 2016 at 21:26