Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The fundamental group $\Pi_1(G)$ of a connected graph $G$ is defined to consist of all loops (i.e., closed paths) based at a given fixed basepoint/vertex $g \in G$ as elements, and concatenation as the group operation. (for $G$ connected, we can show that the group is independent of the choice of basepoint; given $g,g'$ we construct an isomorphism between the two groups by joining $g,g'$ with a path.) Also given a connected graph $G$, there is is a result that $G$ has a spanning tree $T$ -- a tree $T\lt G$ that uses all vertices in $G$ ).

Now, the main result (all else was a set-up until now) is that $\Pi_1(G) \sim \mathrm{Gp}({E(T-G)})$, i.e., $\Pi_1(G)$ is the free group generated by all edges in $G$ that are not in $T$.

My doubt is about this isomorphism; I do see how we need edges in $T-G$ in order to generate loops based at a point, since $T$ is acyclic (so that if $G=T$, the group is trivial). But I do not see how the group is isomorphic to the free group generated by edges in $T-G$. This is what I have so far: let $f_i$ denote a free edge, i.e., an edge in $T-G$. We can assume there is just one path joining any two edges in $T$ (otherwise, $T$ would contain a cycle) Given $g$ fixed in $G$ (assume WOLG $g$ in $T$), I think every closed loop based at $g$ can be realized as the concatenation of a path within $T$, and an edge $f_i$ (aka, a path in $G-T$), and then a(the) path from an endpoint of $f_i$ to $g$ again. Then, for any edge $f_i$, there is a (class) of loops based at $g$. Question: is the above the sketch of a proof for the fact that $\Pi_1(G)$ is the free group generated by all the edges in $G-T$?

Sorry, I did not know how to make the question any more concise; I hope I don't get any Courics for writing too-long of a question.


share|cite|improve this question
The above tells you how you get the group. The fact that it's free, though, takes a bit more work (you need to show that no concatenation of such paths is equivalent to the trivial path, unless you are simply "undoing" what you did; that is, no nontrivial word in the group equals the identity). – Arturo Magidin Mar 2 '11 at 4:53
Thanks, Arturo: are you saying that I have shown that the fi generate Pi_1(G), but that I need to argue that Pi_1(G) is free?I think it is straightforward to show that the only possible relation would have to be obtained by reversing a loop. Maybe I need to specify more clearly when/how based loops would be considered pairwise-equivalent, to show that the only relations are the "necesssary ones", i.e., given paths p1,p2, then p1*p2=e iff p2 undoes p1, i.e., p1 reverses the direction of every edge in p1.I 'm working on it; will post if I get it. – Herb Mar 2 '11 at 5:25
It's possible you already know that the fundamental groups of certain kinds of spaces are free (though I doubt it, since this is usually what is used to prove it). But yes: you have shown the group is generated by certain elements, but you have not proven that it is free in those elements. Proving it is not difficult, granted, but it still needs to be done. – Arturo Magidin Mar 2 '11 at 20:52
You can be much more precise. Just take any loop, look at the edges that are in $G \backslash T$ for each, you can decompose the loop as the concatenation of loops that traverse that edge (in one way or the other) and only use edges on the tree. This will show that every loop can be written in the free group generated by the edges on $G \backslash T$ (the converse being fairly obvious). – David Kohler Apr 3 '11 at 20:59
Note that your tree $T$ is contractible, which --- when contracted --- produces a bouquet (to see why, study how many vertices there will be)...and that's how this "spanning tree" approach to $\pi_{1}(G)$ relates to the "good, old-fashioned homotopy classes of loops" approach Qiaochu notes below. – Alex Nelson Oct 6 '12 at 23:27

Your description of the fundamental group is not correct, and in fact does not describe a group (as it stands, concatenation is not associative and no non-identity element has an inverse). You need to consider homotopy classes of loops.

The proof I know of the result you want proceeds by showing that you can contract the graph along each edge of the spanning tree to get a wedge of circles, one for each edge not in the spanning tree. Once you know that the fundamental group is a homotopy invariant, and once you know how to describe the fundamental group of a wedge of circles (e.g. using Seifert-van Kampen), the conclusion follows.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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