Graph loops and free groups

Try

A connected graph can have many vertices that only divide routes into shorter segments. Choose a maximal tree connecting all vertices. Its edges supply reference routes; the edges outside the tree supply independent loop generators. For a graph with six vertices and eight edges, a maximal tree uses five edges, leaving three generators.

Predict

Predict whether three graph generators must commute. They do not. A graph has no attached two-dimensional disk imposing a commutator relation. Predict also whether merely counting E−V+1 proves the group is free. The count identifies candidates, but a proof must rule out hidden relations among their words. A covering tree will provide that certificate.

Experiment

Start with the empty word and follow labeled edges in a bouquet cover.

Traversed word	Reduced endpoint
aa⁻¹	Empty
ab	ab
ba	ba
aba⁻¹b⁻¹	aba⁻¹b⁻¹

Cancel adjacent inverse pairs only. The endpoints ab and ba differ, so the corresponding loops cannot be endpoint homotopic once the cover is verified. This is stronger than asserting that their pictures look different.

Understand

For a bouquet of r circles, form a graph whose vertices are finite reduced words in r letters and their inverses. From a word w, an oriented edge labeled a_j runs to the reduced word wa_j. Reversing this edge represents appending the inverse letter. Map every such edge to the corresponding bouquet circle with its orientation.

An interior point of a base edge has a short interval neighborhood lifted to disjoint edge intervals. A small star around the bouquet vertex lifts to disjoint stars: each word vertex has exactly one outgoing and one incoming half-edge for each label. The restrictions are homeomorphisms, so this is a covering. The graph is connected because each reduced word is reached by following its letters. It is a tree because deleting the final letter gives the unique predecessor on a reduced route to the empty word; any nonbacktracking closed route would yield a nonempty reduced word equal to the empty word, impossible by the vertex construction.

Every loop in a finite graph is homotopic to an edge path after subdividing its parameter into vertex-star and edge-interval neighborhoods and straightening inside those contractible pieces. A reduced nonempty bouquet word lifts to a different vertex, so homotopy lifting prevents it from being null. Adjacent inverse pairs contract by retracing homotopies. Thus reduced words classify loop classes, with concatenation followed by reduction: the group is free on the r circles.

For a general finite connected graph choose a maximal tree T. Contract its edges one at a time. Contracting an edge with distinct endpoints is a homotopy equivalence: choose one endpoint as representative, route the incident edges from the other endpoint along the contracted edge to build a map back, and slide those inserted segments to give the two homotopies. The operation preserves the graph outside this local routing. Repeating on the V−1 tree edges leaves one vertex and E−V+1 circle edges, proving the rank formula. Equivalently the tree paths provide connectors for every non-tree generator.

Apply

A finite tree is contractible by successively retracting leaf edges. The covering tree above is infinite; any particular loop has compact image and can be reduced within finitely many locally finite edges, so it also contracts. Do not claim an arbitrary infinite tree contracts by finishing infinitely many leaf removals in a finite argument.

Continue

The free-group computation establishes noncommutativity and supplies explicit normal forms. Attaching disks will impose relations on those words. Next, the boundary word of an attached two-cell will explain why a torus has commuting generators while a projective plane has a generator of order two.

Continue to Cell attachments and surface groups.