In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, a branch of
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the (binary) cycle space of an
undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
is the set of its
even-degree subgraphs.
This set of subgraphs can be described
algebra
Algebra is a branch of mathematics that deals with abstract systems, known as algebraic structures, and the manipulation of expressions within those systems. It is a generalization of arithmetic that introduces variables and algebraic ope ...
ically as a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
over the two-element
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
. The
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coo ...
of this space is the
circuit rank of the graph. The same space can also be described in terms from
algebraic topology
Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariant (mathematics), invariants that classification theorem, classify topological spaces up t ...
as the first
homology group
In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the ''homology of a chain complex'', resulting in a sequence of abelian grou ...
of the graph. Using homology theory, the binary cycle space may be generalized to cycle spaces over arbitrary
ring
(The) Ring(s) may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
Arts, entertainment, and media Film and TV
* ''The Ring'' (franchise), a ...
s.
Definitions
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
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
, or as a
homology group
In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the ''homology of a chain complex'', resulting in a sequence of abelian grou ...
.
Graph theory
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 2
''m'' spanning subgraphs, including ''G'' itself as well as the
empty graph
In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
Order-zero graph
The order-zero graph, , is t ...
on the same set of vertices as ''G''. The collection of all spanning subgraphs of a graph ''G'' forms the
edge space of ''G''.
[.][.]
A graph ''G'', or one of its subgraphs, is said to be
Eulerian if each of its vertices has an
even number
In mathematics, parity is the property of an integer of whether it is even or odd. An integer is even if it is divisible by 2, and odd if it is not.. For example, −4, 0, and 82 are even numbers, while −3, 5, 23, and 69 are odd numbers.
The ...
of incident edges (this number is called the
degree of the vertex). This property is named after
Leonhard Euler
Leonhard Euler ( ; ; ; 15 April 170718 September 1783) was a Swiss polymath who was active as a mathematician, physicist, astronomer, logician, geographer, and engineer. He founded the studies of graph theory and topology and made influential ...
who proved in 1736, in his work on the
Seven Bridges of Königsberg
The Seven Bridges of Königsberg is a historically notable problem in mathematics. Its negative resolution by Leonhard Euler, in 1736, laid the foundations of graph theory and prefigured the idea of topology.
The city of Königsberg in Prussia ...
, that a
connected graph
In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgrap ...
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.
Algebra
If one applies any
set operation such as union or intersection of sets to two spanning subgraphs of a given graph, the result will again be a subgraph. In this way, the edge space of an arbitrary graph can be interpreted as a
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...
.

The cycle space, also, has an algebraic structure, but a more restrictive one. The union or intersection of two Eulerian subgraphs may fail to be Eulerian. However, the
symmetric difference
In mathematics, the symmetric difference of two sets, also known as the disjunctive union and set sum, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and ...
of two Eulerian subgraphs
(the graph consisting of the edges that belong to exactly one of the two given graphs) is again Eulerian.
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
neighbourhood
A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neighbourh ...
s 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
In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...
over the two-element
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
. This field has two elements, 0 and 1, and its addition and multiplication operations can be described as the familiar addition and multiplication of
integer
An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
s, taken
modulo 2. 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 space
Real may refer to:
Currencies
* Argentine real
* Brazilian real (R$)
* Central American Republic real
* Mexican real
* Portuguese real
* Spanish real
* Spanish colonial real
Nature and science
* Reality, the state of things as they exist, ...
s. 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
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...
, and multiplication by the scalar 0 takes every element to the empty graph, which forms the
additive identity
In mathematics, the additive identity of a set that is equipped with the operation of addition is an element which, when added to any element in the set, yields . One of the most familiar additive identities is the number 0 from elementary ma ...
element for the cycle space.
The edge space is also a vector space over
with the symmetric difference as addition. As vector spaces, the cycle space and the
cut space of the graph (the family of edge sets that span the
cuts of the graph) are the
orthogonal complement
In the mathematical fields of linear algebra and functional analysis, the orthogonal complement of a subspace W of a vector space V equipped with a bilinear form B is the set W^\perp of all vectors in V that are orthogonal to every vector in W. I ...
s of each other within the edge space. This means that a set
of edges in a graph forms a cut if and only if every Eulerian subgraph has an even number of edges in common with
, and
forms an Eulerian subgraph if and only if every cut has an even number of edges in common with
.
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
if and only if
has an even number of
spanning forest
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
s.
Topology
An undirected graph may be viewed as a
simplicial complex
In mathematics, a simplicial complex is a structured Set (mathematics), set composed of Point (geometry), points, line segments, triangles, and their ''n''-dimensional counterparts, called Simplex, simplices, such that all the faces and intersec ...
with its vertices as zero-dimensional simplices and the edges as one-dimensional simplices.
[.] The
chain complex
In mathematics, a chain complex is an algebraic structure that consists of a sequence of abelian groups (or modules) and a sequence of homomorphisms between consecutive groups such that the image of each homomorphism is contained in the kernel o ...
of this topological space consists of its edge space and
vertex space
In the mathematical discipline of graph theory, the edge space and vertex space of an undirected graph are vector spaces defined in terms of the edge and vertex sets, respectively. These vector spaces make it possible to use techniques of linear ...
(the Boolean algebra of sets of vertices), connected by a boundary operator that maps any spanning subgraph (an element of the edge space) to its set of odd-degree vertices (an element of the vertex space). The
homology group
In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the ''homology of a chain complex'', resulting in a sequence of abelian grou ...
:
consists of the elements of the edge space that map to the zero element of the vertex space; these are exactly the Eulerian subgraphs. Its group operation is the symmetric difference operation on Eulerian subgraphs.
Replacing
in this construction by an arbitrary
ring
(The) Ring(s) may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
Arts, entertainment, and media Film and TV
* ''The Ring'' (franchise), a ...
allows the definition of cycle spaces to be extended to cycle spaces with coefficients in the given ring, that form
modules over the ring.
In particular, the integral cycle space is the space
:
It can be defined in graph-theoretic terms by choosing an arbitrary
orientation
Orientation may refer to:
Positioning in physical space
* Map orientation, the relationship between directions on a map and compass directions
* Orientation (housing), the position of a building with respect to the sun, a concept in building des ...
of the graph, and defining an integral cycle of a graph
to be an assignment of integers to the edges of
(an element of the
free abelian group
In mathematics, a free abelian group is an abelian group with a Free module, basis. Being an abelian group means that it is a Set (mathematics), set with an addition operation (mathematics), operation that is associative, commutative, and inverti ...
over the edges) with the property that, at each vertex, the sum of the numbers assigned to incoming edges equals the sum of the numbers assigned to outgoing edges.
[.]
A member of
or of
(the cycle space modulo
) with the additional property that all of the numbers assigned to the edges are nonzero is called a
nowhere-zero flow or a nowhere-zero
-flow respectively.
Circuit rank
As a vector space, the dimension of the cycle space of a graph with
vertices,
edges, and
connected components is
.
[.] This number can be interpreted topologically as the first
Betti number
In algebraic topology, the Betti numbers are used to distinguish topological spaces based on the connectivity of ''n''-dimensional simplicial complexes. For the most reasonable finite-dimensional spaces (such as compact manifolds, finite simplicia ...
of the graph.
In graph theory, it is known as the
circuit rank, cyclomatic number, or nullity of the graph.
Combining this formula for the rank with the fact that the cycle space is a vector space over the two-element field shows that the total number of elements in the cycle space is exactly
.
Cycle bases
A
basis of a vector space is a minimal subset of the elements with the property that all other elements can be written as a linear combination of basis elements. Every basis of a finite-dimensional space has the same number of elements, which equals the dimension of the space. In the case of the cycle space, a basis is a family of exactly
Eulerian subgraphs, with the property that every Eulerian subgraph can be written as the symmetric difference of a family of basis elements.
Existence
By
Veblen's theorem, 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. Therefore, it is always possible to find a basis in which the basis elements are themselves all simple cycles. Such a basis is called a
cycle basis of the given graph. More strongly, it is always possible to find a basis in which the basis elements are
induced cycles or even (in a
3-vertex-connected graph)
non-separating induced cycles.
Fundamental and weakly fundamental bases
One way of constructing a cycle basis is to form a
maximal forest of the graph, and then for each edge
that does not belong to the forest, form a cycle
consisting of
together with the path in the forest connecting the endpoints of
. The cycles
formed in this way are linearly independent (each one contains an edge
that does not belong to any of the other cycles) and has the correct size
to be a basis, so it necessarily is a basis. A basis formed in this way is called a fundamental cycle basis (with respect to the chosen forest).
If there exists a linear ordering of the cycles in a cycle basis such that each cycle includes at least one edge that is not part of any previous cycle, then the cycle basis is called weakly fundamental. Every fundamental cycle basis is weakly fundamental (for all linear orderings) but not necessarily vice versa. There exist graphs, and cycle bases for those graphs, that are not weakly fundamental.
[.]
Minimum weight bases
If the edges of a graph are given real number weights, the weight of a subgraph may be computed as the sum of the weights of its edges. The minimum weight basis of the cycle space is necessarily a cycle basis, and can be constructed in polynomial time.
The minimum weight basis is not always weakly fundamental, and when it is not it is
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
to find the weakly fundamental basis with the minimum possible weight.
Planar graphs
Homology
If a
planar graph
In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
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.
The boundary of a 2-chain is necessarily an Eulerian subgraph, and every Eulerian subgraph can be generated in this way from exactly two different 2-chains (each of which is the
complement of the other).
[, pp. 105–106.] 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
Mac Lane's planarity criterion
In graph theory, Mac Lane's planarity criterion is a characterisation of planar graphs in terms of their cycle spaces, named after Saunders Mac Lane who published it in 1937. It states that a finite undirected graph is planar if and only if
the c ...
, named after
Saunders Mac Lane
Saunders Mac Lane (August 4, 1909 – April 14, 2005), born Leslie Saunders MacLane, was an American mathematician who co-founded category theory with Samuel Eilenberg.
Early life and education
Mac Lane was born in Norwich, Connecticut, near w ...
, characterizes planar graphs in terms of their cycle spaces and cycle bases. It states that a finite undirected graph is planar if and only if the graph has a cycle basis in which each edge of the graph participates in at most two basis cycles. 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. Conversely, if a cycle basis has at most two cycles per edge, then its cycles can be used as the set of bounded faces of a planar embedding of its graph.
Duality
The cycle space of a planar graph is the
cut space of its
dual graph
In the mathematics, mathematical discipline of graph theory, the dual graph of a planar graph is a graph that has a vertex (graph theory), vertex for each face (graph theory), face of . The dual graph has an edge (graph theory), edge for each p ...
, and vice versa.
The minimum weight cycle basis for a planar graph is not necessarily the same as the basis formed by its bounded faces: it can include cycles that are not faces, and some faces may not be included as cycles in the minimum weight cycle basis. There exists a minimum weight cycle basis in which no two cycles cross each other: for every two cycles in the basis, either the cycles enclose disjoint subsets of the bounded faces, or one of the two cycles encloses the other one. Following the duality between cycle spaces and cut spaces, this basis for a planar graph corresponds to a
Gomory–Hu tree of the dual graph, a minimum weight basis for its cut space.
Nowhere-zero flows
In planar graphs,
colorings with
distinct colors are dual to nowhere-zero flows over the ring
of integers modulo
. In this duality, the difference between the colors of two adjacent regions is represented by a flow value across the edge separating the regions. In particular, the existence of nowhere-zero 4-flows is equivalent to the
four color theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions shar ...
. The
snark theorem generalizes this result to nonplanar graphs.
[
]
References
{{reflist, 30em
Algebraic graph theory