Free Graphs, An Introduction

Introduction

This topic is a confluence of graph theory, free groups, covering spaces, and singular and cellular homology. If you are familiar with these concepts, this is a lovely and unexpected synergy.

Throughout this topic, a graph is a digraph, where each arrow implies the reverse arrow. This looks like a regular graph, but it matters whether you move from a to b or from b to a. This definition is motivated by singular homology, where a 1 simplex travels specifically from one vertex to another.

The graph can have multiple edges and loops. Remember that a loop has two arrows running around in both directions.

A graph has at least one vertex.

Given a graph, an orientation selects a particular direction for each edge. (This may require the axiom of choice.) The preferred direction is the edge, the other direction is the inverse of the edge. It's a bit of a diversion, but an oriented graph can act as a category. Vertices are objects, and paths are morphisms. A path is a finite sequence of edges and inverse edges, depending on whether you are traveling with or against the orientation. A point is a degenerate path, and acts as the identity morphism on that object.

A reduced path has no backtracking. You never go from a to b and back to a; at least not along the same edge. Nor can you travel around a loop and back again. Returning to the world of categories, antiparallel arrows are inverse morphisms. There is no point in applying a function, and then its inverse. Similarly, you can reduce a path by cancelling any backtracking. This reduction is unique. Cancel edges and inverse edges, wherever they appear, in any order, and find the same reduced path. To prove this, associate each edge with a generator in a free group. Paths are words, and reduced paths are reduced words. Edges cancel iff adjacent symbols cancel. We know, from free groups, that the reduced word is unique; hence the reduced path is unique.

Don't assume this is a perfect correspondence. Paths map into, but not onto, the words of the free group. For instance, if the edge e moves from a to b, one cannot realize the word ee as a path. If you want a graph that is isomorphic to a free group F, let v be the only vertex, and create one bidirectional loop for each generator of F.

Homotopy Classes

If a path moves from a to b, and then from b to a, along the same edge, this portion of the path can be contracted back to a. Thus every path is homotopic to its reduction.

Let G be a graph, and view it as a 1 dimensional cw complex. Let T be a spanning tree for G. The π groups of G are now well understood, along with its homology. Both are free groups, generated by the cycle basis, but π₁(G) is free nonabelian, and h₁(G) is free abelian. Associate each chord, i.e. each edge in the cycle basis, with a generator in the free group F, and π₁(G) = F.

Subgraph

Let H be a subgraph of G. One can build a spanning tree for G, based on any initial tree that is contained in G. Find a spanning tree for each component of H. Starting with this forest, build a spanning tree for each component of G. Every chord in H becomes a generator for its fundamental group, or its first homology. This is also a generator for π₁(G) or h₁(G). Therefore, inclusion embeds π₁(H) into π₁(G), and h₁(H) into h₁(G).

This does not hold in general topology. When a circle embeds in the sphere, its fundamental group disappears.