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.
Two a-arrows leave 0. Fold them together, identifying their endpoints. This is the entire construction in this example.
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 form a free basis. 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. Make a new graph whose vertices are pairs of vertices. 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. The refactor succeeds because free cancellation and graph folding fit exactly.
What changed, and where to continue
We replaced a search through generator products with deterministic local moves, and justified the replacement. The same object then supplied a basis and an intersection algorithm. That is the gain: the graph makes several formerly separate questions elementary operations on one 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. This exposition introduces that established method; it makes no claim of a new theorem.
For a different group-theoretic refactor, Six Elements, One Comparison develops a common comparison of quotients. Folding answers questions about words in free groups; quotient comparison answers questions about decompositions. Neither needs to be presented as the compulsory route to the other.