Cycle space

The set of edges of a graph can be made into a Z₂-vector space by taking the symmetric difference as addition (ie an edge is in the sum if it is in exactly an odd number of the summands). The resulting vector space is called the edge space of the graph.

An important subspace of the edge space is the cycle space. It consists of (the edge sets of) all the cycles of the graph and of all sums of cycles. The addition of two cycles (shown dashed) is illustrated in the figure. Note that the result here (also shown dashed) is not a cycle.

There are a number of basic results concerning the cycle space. Firstly, the elements of the cycle space can be characterized by the cuts: A set of edges is an element of the cycle space if and only if it meets every cut in a finite number of edges.

Secondly, the dimension of the cycle space is related to the number of vertices of and edges of the graph. If the graph has n vertices and m edges then the dimension is: dim = m-n+1.

Thirdly, the cycle space is generated by the fundamental cycles of every spanning tree.

An important application of the cycle space is Mac Lane's planarity criterion, which gives an algebraic characterization of the planar graphs.

References:

• R. Diestel, Graph Theory (2nd edition), Springer-Verlag, 2000