Editing Cycle space (section)

==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]], or as a [[homology group]].

===Graph theory===
A [[Glossary of graph theory#Subgraphs|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 [[Vertex (graph theory)|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<sup>''m''</sup> 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''.<ref name="gy">{{citation|title=Graph Theory and Its Applications|edition=2nd|first1=Jonathan L.|last1=Gross|first2=Jay|last2=Yellen|publisher=CRC Press|year=2005|isbn=9781584885054|chapter=4.6 Graphs and Vector Spaces|pages=197–207|url=https://books.google.com/books?id=-7Q_POGh-2cC&pg=PA197}}.</ref><ref name="diestel">{{citation|title=Graph Theory|volume=173|series=Graduate Texts in Mathematics|first=Reinhard|last=Diestel|publisher=Springer|year=2012|chapter=1.9 Some linear algebra|pages=23–28|url=https://books.google.com/books?id=eZi8AAAAQBAJ&pg=PA23}}.</ref>

A graph ''G'', or one of its subgraphs, is said to be [[Eulerian graph|Eulerian]] if each of its vertices has an [[even number]] of incident edges (this number is called the [[degree (graph theory)|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.<ref name="gy"/><ref name="diestel"/>

===Algebra===
If one applies any [[Set (mathematics)#Basic operations|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 (structure)|Boolean algebra]].<ref>{{citation|title=Applied Discrete Structures|first=K. D.|last=Joshi|publisher=New Age International|year=1997|isbn=9788122408263|page=172|url=https://books.google.com/books?id=lxIgGGJXacoC&pg=PA172}}.</ref>

[[File:Cycle space addition.svg|thumb|360px|The symmetric difference of two Eulerian subgraphs (red and green) is a Eulerian subgraph (blue).]]
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]] of two Eulerian subgraphs
(the graph consisting of the edges that belong to exactly one of the two given graphs) is again Eulerian.<ref name="gy"/> 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 (graph theory)|neighbourhood]]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]] over the two-element [[finite field]] [[GF(2)|<math>\Z_2</math>]].<ref>{{citation|title=A Beginner's Guide to Graph Theory|first=W. D.|last=Wallis|publisher=Springer|year=2010|isbn=9780817645809|page=66|url=https://books.google.com/books?id=240QO32GJOcC&pg=PA66}}.</ref> 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]]s, taken [[Modular arithmetic|modulo&nbsp;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]]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&nbsp;1 is the [[identity operation]], and multiplication by the scalar&nbsp;0 takes every element to the empty graph, which forms the [[additive identity]] element for the cycle space.

The edge space is also a vector space over <math>\Z_2</math> 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 [[Cut (graph theory)|cuts]] of the graph) are the [[orthogonal complement]]s of each other within the edge space. This means that a set <math>S</math> of edges in a graph forms a cut if and only if every Eulerian subgraph has an even number of edges in common with <math>S</math>, and <math>S</math> forms an Eulerian subgraph if and only if every cut has an even number of edges in common with <math>S</math>.<ref name="diestel"/> 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 <math>G</math> if and only if <math>G</math> has an even number of [[spanning forest]]s.<ref>{{citation|first=David|last=Eppstein|authorlink=David Eppstein|title=On the Parity of Graph Spanning Tree Numbers|year=1996|url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf|series=Technical Report 96-14|publisher=Department of Information and Computer Science, University of California, Irvine}}.</ref>

===Topology===
An undirected graph may be viewed as a [[simplicial complex]] with its vertices as zero-dimensional simplices and the edges as one-dimensional simplices.<ref name="serre">{{citation|title=Trees|first=Jean-Pierre|last=Serre|authorlink=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003|url=https://books.google.com/books?id=MOAqeoYlBMQC&pg=PA23|isbn=9783540442370}}.</ref> The [[chain complex]] of this topological space consists of its edge space and [[vertex space]] (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]]
:<math>H_1(G,\Z_2)</math>
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 <math>\Z_2</math> in this construction by an arbitrary [[ring (mathematics)|ring]] allows the definition of cycle spaces to be extended to cycle spaces with coefficients in the given ring, that form [[module (mathematics)|module]]s over the ring.<ref>{{citation|title=Algebraic Graph Theory|series=Cambridge Mathematical Library|first=Norman|last=Biggs|publisher=Cambridge University Press|year=1993|isbn=9780521458979|page=154|url=https://books.google.com/books?id=6TasRmIFOxQC&pg=PA154}}.</ref>
In particular, the '''integral cycle space''' is the space
:<math>H_1(G,\Z).</math>
It can be defined in graph-theoretic terms by choosing an arbitrary [[orientation (graph theory)|orientation]] of the graph, and defining an '''integral cycle''' of a graph <math>G</math> to be an assignment of integers to the edges of <math>G</math> (an element of the [[free abelian group]] 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.<ref name="mcba">{{citation|title=Algorithmics of Large and Complex Networks|series=Lecture Notes in Computer Science|volume=5515|year=2009|pages=34–49|contribution=Minimum cycle bases and their applications|first1=Franziska|last1=Berger|first2=Peter|last2=Gritzmann|first3=Sven|last3=de Vries|doi=10.1007/978-3-642-02094-0_2|isbn=978-3-642-02093-3}}.</ref>

A member of <math>H_1(G,\Z)</math> or of <math>H_1(G,\Z_k)</math> (the cycle space modulo <math>k</math>) 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 <math>k</math>-flow respectively.<ref>{{citation
 | last = Seymour | first = P. D. | authorlink = Paul Seymour (mathematician)
 | contribution = Nowhere-zero flows
 | location = Amsterdam
 | mr = 1373660
 | pages = 289–299
 | publisher = Elsevier
 | title = Handbook of combinatorics, Vol. 1, 2
 | year = 1995}}.</ref>