Cycle Space - The Integral Cycle Space

The Integral Cycle Space

The foregoing development can be carried out over the integers, Z. The integral edge space is the abelian group ZE of functions from the edge set E to the integers. It is necessary (for the notation) to choose an arbitrary orientation of the graph in order to define the cycle space, but the definition does not depend on that choice. An integral cycle is a function such that the sum of values on edges oriented into a vertex x equals the sum of values on edges oriented out of x, for every vertex x. The set of integral cycles is a subgroup of the integral edge space. A cycle that never takes the value zero is called nowhere zero.

Reversing the orientation of an edge negates the value of a cycle on that edge. It is in this sense that the theory is independent of the arbitrary orientation. Given any one cycle, the orientation can be chosen so that cycle takes only nonnegative values.

An integral cycle whose maximum absolute value on any edge is less than k, a positive integer, is sometimes called a k-flow on G. W.T. Tutte developed an extensive theory of nowhere-zero k-flows that is in some ways dual to that of graph coloring.