Graphs, Cycle Basis

Cycle Basis

Consider the union of two cycles, minus their common edges. This is similar to an exclusive or operation. If the cycles are the same they annihilate each other, leaving a graph of isolated points. If they are distinct we have two disconnected cycles. If they intersect, follow the common edges until the two cycles diverge. Follow both cycles until they join back up again - you have built a cycle in the product. Follow the common edges again until they diverge, whence you build another cycle. Continue until you are back to start. The exclusive or of two cycles is a set of edge-disjoint cycles. Note that two cycles could have a vertex in common, such as two triangles joined at a point.

The union of edge disjoint cycles can be xored with another union of edge disjoint cycles. We want to prove the result is a union of edge disjoint cycles. It is enough to add one cycle at a time to a disjoint union U. If the result is a disjoint union after each step, then we have a disjoint union at the end.

Proceed by induction on the number of common edges; common between the new cycle and U. If the new cycle has no edges in common with U, the result is clearly a union of disjoin cycles. So assume the new cycle has at least one edge in common with the first cycle of U. Merge these two cycles together to build V, new cycles that are disjoint from one another. Now fold V into the remaining cycles of U. Each cycle exhibits fewer common edges than the first cycle, so by induction, the result is a union of disjoint cycles. In conclusion, the merging of two unions of disjoint cycles produces another union of disjoint cycles.

These cycle collections form a boolean vector space, whose basis is easily constructed. The result is called the "cycle basis". Draw a spanning tree, and let every remaining edge act as a basis element. Each edge joins the spanning tree to make a corresponding cycle. Remember, there is only one path in the tree connecting the end points of the basis edge, so each basis edge defines one cycle. Since the basis edges are linearly independent, the resulting cycles are also linearly independent. We have a vector space of cycles, where addition takes place in Z₂, that is, the exclusive or operator.

Does this vector space span all collections of cycles? It is enough to show it spans every cycle. Consider a cycle C, which contains a set S of basis edges. The path from the first basis edge to the second is fixed. It is wholly contained in the spanning tree, and there can be but one such path. This holds true as we move from edge to edge in S. The cycle is uniquely determined by S. Let T be the basis cycles corresponding to the basis edges in S. Let D be the cycle, or union of cycles, produced by adding up the cycles in T. Then consider C+D. All the basis edges go away. Now C+D has to be a union of cycles, yet it lives in the spanning tree. Thus C+D = 0, and C = D. Our original cycle is spanned, and all cycle unions are spanned. The dimension of the vector space is e-(v-1), the number of edges beyond the spanning tree.

All this works on an infinite graph. If T₁ and T₂ are subgraphs of G, and are both trees, then T₁ ≤ T₂ if T₁ is a subgraph of T₂. Take the union of an ascending chain of trees to find another tree. It is connected, because every two vertices are connected at a lower level. And it has no cycles, because a cycle would appear at a lower level. Thus we can use zorn's lemma to assert the existence of a maximal tree in G, which must be a spanning tree. The other edges of G, sometimes called chords, generate the cycle basis. Each cycle is finite, with finitely many chords, and is in the span of our basis, as shown above. The vector space is the set of finite unions of disjoint cycles, and its dimension is equal to the number of chords.