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...

  • 2
    $\begingroup$ 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. $\endgroup$ – gary Sep 12 '11 at 0:36
  • $\begingroup$ Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help! $\endgroup$ – William Sep 12 '11 at 14:48
  • $\begingroup$ 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 . $\endgroup$ – gary Sep 12 '11 at 16:20
  • $\begingroup$ thanks gary. do you have a link to the proof? $\endgroup$ – William Sep 12 '11 at 17:47
  • $\begingroup$ 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. $\endgroup$ – gary Sep 12 '11 at 18:05

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$.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Arturo Magidin Sep 16 '11 at 20:28
  • $\begingroup$ @Arturo I think you meant "edges" in the first line. :) $\endgroup$ – Srivatsan Sep 16 '11 at 21:21
  • $\begingroup$ @Srivatsan: Oops; quite so. Too bad I can't edit it anymore... $\endgroup$ – Arturo Magidin Sep 17 '11 at 4:20
  • 3
    $\begingroup$ 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. $\endgroup$ – Eric Wofsey Dec 22 '16 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.