RefacteA subgroup given by words can be hard to inspect. A small labelled graph changes the task: membership becomes following a path. The important step is proving that the graph remembers exactly the subgroup we started with.
Words that hide a simple question
Work in the free group F(a, b). Its elements are words in a, b and their inverses, reduced by cancelling adjacent inverse pairs. Multiplication concatenates words and reduces. Let H be the subgroup generated by a2 and ab. Is a given reduced word in H?
One approach searches through products of the two generators and their inverses. The search hides useful information in repeated cancellations. We will instead build an object that incorporates those cancellations into its local rules.
Build the loops, then fold
Start at a vertex called 0. Draw one loop reading aa and another reading ab, giving each an intermediate vertex. Every arrow may also be followed backwards, with its label inverted. The closed walks at 0 represent exactly products of our generators and their inverses.
We want to read an input word one letter at a time without searching among several possible continuations. At present, the first letter a offers two choices. Make that choice unique by identifying the two a-arrows and their endpoints. This operation is called a fold. It gives the required deterministic reading rule, but we must still check that the identification has not changed the represented subgroup.
Why the fold preserves the answer
Every old closed walk remains a closed walk after folding, with the same label. The converse needs an argument: identifying vertices might otherwise create unwanted words.
Here a new walk may switch between what used to be vertices u and v. Before folding, connect them by travelling backwards along the first a-edge and forwards along the second. That detour reads a−1a, which cancels. Insert this detour whenever a lifted walk needs to switch sides. The result is an old closed walk representing the same free-group element. Thus the fold preserves the represented subgroup.
The general Stallings folding procedure repeatedly identifies equally labelled arrows with the same starting vertex, including inverse arrows. Each fold reduces the finite graph, so the process terminates. The same cancellation argument justifies each step. In the resulting graph there is at most one outgoing arrow for each signed letter at each vertex.
Membership becomes a walk
Reduce the input word, start at 0, and follow its letters. A missing arrow or a different final vertex means rejection; returning to 0 means membership. For this graph:
| Word | What happens | In H? |
|---|---|---|
| a2 | 0 → 1 → 0 | Yes |
| ab | 0 → 1 → 0 | Yes |
| a−1b | Reverse the returning a-arrow, then follow b | Yes |
| a | Ends at 1 | No |
| b | No b-arrow leaves 0 | No |
The third answer can be checked in the original generators: a−1b = (a2)−1(ab). The graph has made this cancellation available without a search through products.
A basis from a spanning tree
Choose the outgoing a-edge as a spanning tree. Each remaining edge gives a closed walk: reach its start along the tree, cross the edge, and return along the tree.
These walks generate every closed walk. Insert the tree path from 0 to each intermediate vertex and its reverse between successive edges. The inserted paths cancel in pairs, expressing the original walk as a product of the displayed loops and their inverses; tree edges contribute only backtracking. They are independent as well. Contract the tree and record each remaining edge by its own letter. Removing backtracking deletes inverse pairs of these letters, so a nonempty freely reduced product of the proposed generators cannot reduce to the empty walk.
To transfer this basis to the subgroup, check the original edge labels. In a folded graph, consecutive inverse labels must traverse an edge and its reverse: the reverse edge is the unique outgoing edge with that inverse label. Thus a reduced nonempty edge path has a reduced nonempty label word. The label map therefore introduces no additional relation, and the closed walks above give a free basis of the represented subgroup.
Here they read a2 and ab. In a connected finite graph the count is E − V + 1, counting each edge together with its reverse once. We have 3 − 2 + 1 = 2 generators.
Intersection becomes synchronisation
Now suppose finite folded graphs represent subgroups H and K. Membership in their intersection asks for the same word to be accepted by both graphs. While reading that word, the information we need is the current vertex in each graph. Use that pair as a new state. A letter can be followed from a pair exactly when it can be followed in both coordinates. Start at the pair of starting vertices.
A reduced word returns to that pair exactly when it returns in both original graphs: exactly when it lies in H ∩ K. Keep the starting component and remove edges that occur in no reduced closed walk based there. This gives the subgroup graph for the intersection. It is finite, and a spanning tree supplies a finite basis. We have both an algorithm and a proof of Howson’s theorem: the intersection of two finitely generated subgroups of a free group is finitely generated.
Completing a graph changes the subgroup
A finite-index subgroup has a complete graph: every signed letter can be followed from every vertex. Its index is the number of vertices. Our graph is incomplete, so H has infinite index. Adding a b-arrow from 0 to 1 would complete it, but would enlarge the subgroup: b2 would now be accepted. Completion can construct a finite-index overgroup; it does not preserve the original membership problem.
The free-group hypothesis matters throughout. Additional relations change which words are equal, so this finite machine does not automatically solve subgroup membership in an arbitrary group.
Sources and another graph construction
The method is due to Stallings. For a detailed combinatorial treatment, see Ilya Kapovich and Alexei Myasnikov, Stallings foldings and subgroups of free groups, especially the subgroup, finite-index and product-graph constructions.
For finite groups, the transporter graph keeps two witness words while searching by left and right multiplication. Its closed comparisons recover subgroup intersections attached to different components.