Cycle space

This set of subgraphs can be described algebraically as a vector space over the two-element finite field.

The dimension of this space is the circuit rank of the graph.

The same space can also be described in terms from algebraic topology as the first homology group of the graph.

The cycle space of a graph can be described with increasing levels of mathematical sophistication as a set of subgraphs, as a binary vector space, or as a homology group.

A spanning subgraph of a given graph G may be defined from any subset S of the edges of G. The subgraph has the same set of vertices as G itself (this is the meaning of the word "spanning") but has the elements of S as its edges.

Thus, a graph G with m edges has 2m spanning subgraphs, including G itself as well as the empty graph on the same set of vertices as G. The collection of all spanning subgraphs of a graph G forms the edge space of G.[1][2] A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has an even number of incident edges (this number is called the degree of the vertex).

This property is named after Leonhard Euler who proved in 1736, in his work on the Seven Bridges of Königsberg, that a connected graph has a tour that visits each edge exactly once if and only if it is Eulerian.

However, for the purposes of defining cycle spaces, an Eulerian subgraph does not need to be connected; for instance, the empty graph, in which all vertices are disconnected from each other, is Eulerian in this sense.

The cycle space of a graph is the collection of its Eulerian spanning subgraphs.

In this way, the edge space of an arbitrary graph can be interpreted as a Boolean algebra.

[1] This follows from the fact that the symmetric difference of two sets with an even number of elements is also even.

Applying this fact separately to the neighbourhoods of each vertex shows that the symmetric difference operator preserves the property of being Eulerian.

A family of sets closed under the symmetric difference operation can be described algebraically as a vector space over the two-element finite field

A vector space consists of a set of elements together with an addition and scalar multiplication operation satisfying certain properties generalizing the properties of the familiar real vector spaces.

For the cycle space, the elements of the vector space are the Eulerian subgraphs, the addition operation is symmetric differencing, multiplication by the scalar 1 is the identity operation, and multiplication by the scalar 0 takes every element to the empty graph, which forms the additive identity element for the cycle space.

forms an Eulerian subgraph if and only if every cut has an even number of edges in common with

[2] Although these two spaces are orthogonal complements, some graphs have nonempty subgraphs that belong to both of them.

Such a subgraph (an Eulerian cut) exists as part of a graph

The homology group consists of the elements of the edge space that map to the zero element of the vertex space; these are exactly the Eulerian subgraphs.

[7] In particular, the integral cycle space is the space It can be defined in graph-theoretic terms by choosing an arbitrary orientation of the graph, and defining an integral cycle of a graph

By Veblen's theorem,[11] every Eulerian subgraph of a given graph can be decomposed into simple cycles, subgraphs in which all vertices have degree zero or two and in which the degree-two vertices form a connected set.

[12] One way of constructing a cycle basis is to form a maximal forest of the graph, and then for each edge

[8] The minimum weight basis is not always weakly fundamental, and when it is not it is NP-hard to find the weakly fundamental basis with the minimum possible weight.

[13] If a planar graph is embedded into the plane, its chain complex of edges and vertices may be embedded into a higher dimensional chain complex that also includes the sets of faces of the graph.

The boundary map of this chain complex takes any 2-chain (a set of faces) to the set of edges that belong to an odd number of faces in the 2-chain.

[14] It follows from this that the set of bounded faces of the embedding forms a cycle basis for the planar graph: removing the unbounded face from this set of cycles reduces the number of ways each Eulerian subgraph can be generated from two to exactly one.

Mac Lane's planarity criterion, named after Saunders Mac Lane, characterizes planar graphs in terms of their cycle spaces and cycle bases.

In a planar graph, a cycle basis formed by the set of bounded faces of an embedding necessarily has this property: each edge participates only in the basis cycles for the two faces it separates.

distinct colors are dual to nowhere-zero flows over the ring

The snark theorem generalizes this result to nonplanar graphs.