**Sketch of The Proof Using Bass-Serre Theory**

The following is a sketch of the proof of Grushko's theorem based on the use of foldings techniques for groups acting on trees (see for complete proofs using this argument).

Let *S*={*g*_{1},....,*g*_{n}} be a finite generating set for *G*=*A*∗*B* of size |*S*|=*n*=rank(*G*). Realize *G* as the fundamental group of a graph of groups **Y** which is a single non-loop edge with vertex groups *A* and *B* and with the trivial edge group. Let be the Bass-Serre covering tree for **Y**. Let *F*=*F*(*x*_{1},....,*x*_{n}) be the free group with free basis *x*_{1},....,*x*_{n} and let φ_{0}:*F* → *G* be the homomorphism such that φ_{0}(*x*_{i})=*g*_{i} for *i*=1,...,*n*. Realize *F* as the fundamental group of a graph *Z*_{0} which is the wedge of *n* circles that correspond to the elements *x*_{1},....,*x*_{n}. We also think of **Z**_{0} as a graph of groups with the underlying graph *Z*_{0} and the trivial vertex and edge groups. Then the universal cover of *Z*_{0} and the Bass-Serre covering tree for **Z**_{0} coincide. Consider a φ_{0}-equivariant map so that it sends vertices to vertices and edges to edge-paths. This map is non-injective and, since both the source and the target of the map are trees, this map *"folds"* some edge-pairs in the source. The graph of groups **Z**_{0} serves as an initial approximation for **Y**.

We now start performing a sequence of "folding moves" on **Z**_{0} (and on its Bass-Serre covering tree) to construct a sequence of graphs of groups **Z**_{0}, **Z**_{1}, **Z**_{2}, ...., that form better and better approximations for **Y**. Each of the graphs of groups **Z**_{j} has trivial edge groups and comes with the following additional structure: for each nontrivial vertex group of it there assigned a finite generating set of that vertex group. The *complexity* *c*(**Z**_{j}) of **Z**_{j} is the sum of the sizes of the generating sets of its vertex groups and the rank of the free group *π*_{1}(*Z*_{j}). For the initial approximation graph we have *c*(**Z**_{0})=*n*.

The folding moves that take **Z**_{j} to **Z**_{j+1} can be of one of two types:

- folds that identify two edges of the underlying graph with a common initial vertex but distinct end-vertices into a single edge; when such a fold is performed, the generating sets of the vertex groups and the terminal edges are "joined" together into a generating set of the new vertex group; the rank of the fundamental group of the underlying graph does not change under such a move.
- folds that identify two edges, that already had common initial vertices and common terminal vertices, into a single edge; such a move decreases the rank of the fundamental group of the underlying graph by 1 and an element that corresponded to the loop in the graph that is being collapsed is "added" to the generating set of one of the vertex groups.

One sees that the folding moves do not increase complexity but they do decrease the number of edges in *Z*_{j}. Therefore the folding process must terminate in a finite number of steps with a graph of groups **Z**_{k} that cannot be folded any more. It follows from the basic Bass-Serre theory considerations that **Z**_{k} must in fact be equal to the edge of groups **Y** and that **Z**_{k} comes equipped with finite generating sets for the vertex groups *A* and *B*. The sum of the sizes of these generating sets is the complexity of **Z**_{k} which is therefore less than or equal to *c*(**Z**_{0})=*n*. This implies that the sum of the ranks of the vertex groups *A* and *B* is at most *n*, that is rank(*A*)+rank(*B*)≤rank(*G*), as required.

Read more about this topic: Grushko Theorem

### Famous quotes containing the words theory, sketch and/or proof:

“Frankly, these days, without a *theory* to go with it, I can’t see a painting.”

—Tom Wolfe (b. 1931)

“the vagabond began

To *sketch* a face that well might buy the soul of any man.

Then, as he placed another lock upon the shapely head,

With a fearful shriek, he leaped and fell across the

picture—dead.”

—Hugh Antoine D’Arcy (1843–1925)

“He who has never failed somewhere, that man can not be great. Failure is the true test of greatness. And if it be said, that continual success is a *proof* that a man wisely knows his powers,—it is only to be added, that, in that case, he knows them to be small.”

—Herman Melville (1819–1891)