Motivation
A spanning tree connects all vertices with no redundant edges. Adding one edge creates one cycle; adding several edges creates many overlapping cycles. How can we describe every possible even-degree edge set without listing every cycle separately? The answer is to keep one cycle per non-tree edge and combine those cycles by symmetric difference. This supplies a concrete basis for the cycle space used later in cut and planar-duality arguments.
Definitions
Throughout, is a finite simple undirected graph with vertices, edges and connected components, including isolated vertices.
Definition 1.3.1
(Edge set and even edge set)
An edge set means a subset of together with all original vertices; its degree at a vertex counts only selected incident edges. An edge set is even if every vertex has even degree in it, including degree zero. The empty edge set is even.
Definition 1.3.2
(Symmetric difference and cycle space)
The symmetric difference of edge sets contains the edges occurring in exactly one of . Identifying each edge set with a zero–one vector in turns symmetric difference into addition. The cycle space of is the set of even edge sets with this addition.
At each vertex the parity of the degree in is the sum modulo two of its degree parities in and . Hence the symmetric difference of even sets is even, and the cycle space is a subspace of . It is a space of edge sets, not a set of individual simple cycles.
Definition 1.3.3
(Spanning forest and fundamental cycle)
A spanning forest of is an acyclic edge set containing a spanning tree of each connected component. For an edge outside , the fundamental cycle is the unique – path in together with .
A spanning forest has , including the cases of isolated vertices and the empty graph. Every edge outside has endpoints in the same component, so the – path in exists, and it is unique because is acyclic. The unique edge of outside the forest is itself.
Theorem 1.3.4
(Fundamental cycles form a basis)
For any spanning forest , every even edge set has the unique expression
The empty symmetric difference is empty. Consequently the fundamental cycles are a basis of the cycle space, its dimension is , and it contains exactly edge sets.
Proof
(Proof by eliminating the non-forest edges)
Let be even and put
Each has precisely one non-forest edge, namely . So each non-forest edge occurs in exactly one of the sets being added, apart from itself, and cancels; a non-forest edge outside occurs in none of them. Thus . It is still even, because each fundamental cycle is even and symmetric difference preserves evenness.
An even edge set contained in a forest must be empty. Otherwise its selected subgraph is a nonempty forest; a component with an edge is a nontrivial tree and has a leaf of selected degree one, contradicting evenness. Thus , which is the displayed expression for .
For uniqueness, suppose for some set of non-forest edges. A non-forest edge occurs only in among all fundamental cycles, so if and only if . Hence . In particular the fundamental cycles are independent, and the first part shows they span. There are of them, and the subsets of this basis give different even edge sets.
Proof X-ray
Where acyclicity and spanning are used
The proof uses the two properties of separately. Spanning is used only to guarantee that every non-forest edge has a fundamental cycle at all: its endpoints lie in one component, and connects that component. Acyclicity is used twice: to make the path, and hence , unique, and to show that an even set inside is empty through the leaf argument.
The key move is the observation that each meets the non-forest edges in exactly . In coordinates indexed by the non-forest edges, the fundamental cycles are the standard unit vectors. That single fact both clears the non-forest part of and reads off the coefficients, so existence and uniqueness come from the same observation. The argument closes because what remains is an even set with no room to be nonempty.
Each hypothesis is needed. In a triangle with , which is acyclic but not spanning, no edge has a fundamental cycle, yet the triangle is even. If is the whole triangle, which spans but is not acyclic, there are no non-forest edges, the expression gives only , and the triangle is again missed.
The argument also covers a forest: it has no non-forest edges, and its only even edge set is empty. In a disconnected graph, each fundamental cycle stays inside one component; there is no need to invent an edge joining separate components. Changing the spanning forest changes the basis, but not the even edge sets or their number.
Concept lensAlgebraic
The cycle space as a kernel
Let be the vertex–edge incidence matrix of over . For an edge set with indicator vector , the entry is the selected degree of modulo two. So the cycle space is exactly . By rank–nullity, , and the basis theorem therefore also computes the rank: over . The row of indexed by is the cut , and a sum of rows over a vertex set is , so the row space of is the set of cuts studied below.
The kernel description turns evenness into a linear equation; the next section studies the row space, the cuts.
Cycles, cuts, and parity
Theorem 1.3.5
(Even sets decompose into cycles and meet cuts evenly)
Every nonempty even edge set is an edge-disjoint union of simple cycles. For any vertex set , an even edge set meets the cut in an even number of edges.
Proof
(Proof by peeling cycles and summing degrees)
For the first claim, restrict attention to the subgraph formed by the selected edges and their incident vertices. Every vertex there has positive even degree, hence degree at least two. Take a longest simple path in this subgraph. Every neighbor of its last vertex lies on the path, by maximality, and the last vertex has a neighbor other than its immediate predecessor; that edge closes a simple cycle. Remove its edges. At each of its vertices exactly two selected incidences disappear, so the remaining edge set is even. Repeat until no edges remain. The process terminates because each cycle removes edges. The cycles are edge-disjoint but may share vertices, and the decomposition need not be unique.
For the cut statement, sum selected degrees over the vertices of . Each selected edge internal to contributes two and each selected crossing edge contributes one. The sum is even, so the number of crossing selected edges is even. This proof works for every vertex set, not just one side of a connected separation.
In particular a bridge cannot belong to an even edge set: after deleting a bridge , the vertex set of the component containing one endpoint is a set with , which would have odd intersection. Conversely, an edge that is not a bridge lies on a cycle and therefore belongs to an even set. This is an existence statement, not a claim that every even set contains every non-bridge.
A converse and the size of the cut space
The parity theorem can be turned around. Suppose an edge set meets every cut evenly. Choose the singleton set containing one vertex. The cut of that singleton consists exactly of its incident edges, so even intersection with this cut says that the vertex has even selected degree. Repeating this for each vertex shows that the edge set itself is even. Thus it is enough to check singleton cuts to establish evenness; the preceding theorem then guarantees even intersection with every cut, including cuts with many vertices on both sides.
We can also count distinct cuts. For vertex sets , an edge crosses exactly one of their cuts if and only if it crosses the cut of . Therefore , and cuts form a vector space under symmetric difference. The empty set and the whole vertex set determine the same empty cut; more generally, different vertex sets may determine the same cut. It would be wrong to count all vertex sets as different cuts.
Theorem 1.3.6
(Counting distinct cuts)
For vertex sets , if and only if is a union of entire connected components. Consequently has exactly distinct cuts.
Proof
(Proof through the empty cut)
By the identity above, means that is empty. A vertex set has empty cut exactly when no edge joins it to its complement, which forces it to contain either all or none of each component. There are such unions, including choices about isolated vertices. For any fixed cut, all its representing sets are obtained by toggling one of these component unions. Thus each cut has exactly representations and the number of cuts is . The argument includes the empty graph, where both exponents are zero.
The cycle-space and cut-space dimensions therefore add to .
Counterexample mode
Complementary dimensions do not give a trivial intersection
Claim to test: since the two dimensions add to , the cycle space and the cut space meet only in the empty edge set. Take the four-cycle and . Each of the edges joins a vertex of to one of , so is the whole cycle. The same edge set has selected degree two at every vertex, so it is even. It is a nonempty edge set in both spaces, and the claim is false. What does hold is orthogonality over : every even set meets every cut in an even number of edges. Here the intersection has four edges, which contributes zero to the dot product even though all four edges are shared.
To see why this distinction matters, compare the four-cycle with a separate graph consisting of two vertices and one edge. That edge is a cut but is not even: its two endpoints have selected degree one. Conversely, the whole four-cycle is even and, in this particular graph, is also a cut. An individual cycle need not be a cut in every graph. When moving between the two spaces, verify the relevant definition rather than using a picture that makes an edge set look like a boundary.
The count also illustrates why a component is the correct unit of ambiguity. In a connected graph, switching every vertex from one side of a cut to the other leaves the same crossing edges, giving exactly two representations. In a graph with several components, one can switch the sides independently within each component, because there are no edges between components. Isolated vertices contribute independent switches but can never change a cut edge. This explains the factor without assuming that either side of the cut is connected.
Yes: over the two-element field the cut space is the orthogonal complement of the cycle space.
A natural next question
Are cuts exactly the edge sets that meet every even set evenly?
Yes: over the two-element field the cut space is the orthogonal complement of the cycle space.
Every cut meets every even set evenly, so the cut space lies in the orthogonal complement of the cycle space. Over that complement has dimension , the dimension of the cut space, so the two coincide. Since the fundamental cycles span the cycle space, an edge set is a cut exactly when it meets each fundamental cycle evenly.
Worked examples
Worked example 1.3.7
(A square and one diagonal)
Let the edges be and choose forest . The chords are and . Their fundamental cycles are and . Their symmetric difference cancels and leaves , the other triangle. The four even sets are the empty set, these two fundamental cycles, and their symmetric difference. Here .
Worked example 1.3.8
(Components and isolated vertices count)
Take a triangle on , a separate edge , and an isolated vertex . Then , , . A spanning forest contains two triangle edges and , so there is one fundamental cycle, the triangle, and . The only even sets are empty and the triangle. The edge is a bridge and cannot be selected in an even set; the isolated vertex still contributes to both and .
Worked example 1.3.9
(A union need not be a single cycle)
Let two triangles share exactly one vertex and no edges. Their union is even: the shared vertex has degree four and all other vertices have degree two. It is not a single simple cycle, because the shared vertex would have to be visited twice. Nevertheless it is the edge-disjoint union of two cycles, illustrating why the cycle space contains more than simple cycles.
Common mistakes
Common mistake
(Union is not addition)
Ordinary union is not the addition operation for cycle-space vectors. In the square example, the two fundamental cycles share ; their union is all five edges, and and then have selected degree three. Their symmetric difference cancels both shared edges and is even.
Common mistake
(The dimension is not the number of cycles)
A basis is not the list of all simple cycles, and counts independent binary choices, not simple cycles. The square with one diagonal has three simple cycles, the two triangles and the square, but its cycle space has dimension ; the square is the sum of the two triangles.
Common mistake
(Forgetting isolated vertices in the component count)
The formula is valid only when counts all components, including isolated vertices. For a triangle, a separate edge and an isolated vertex, counting while keeping gives , whereas the triangle shows the dimension is .
Parity is checked in the selected edge set, not in the original graph: a vertex of odd degree in may have even selected degree in an even subset.
Exercises
Quick check
(In the square-with-diagonal example, express the triangle using the fundamental cycles and verify all its selected degrees.)
Use the two chords and .
Solution · Answer
It equals . The selected degrees of are two and that of is zero, so the set is even.
Quick check
(A graph consists of two disjoint triangles and one isolated vertex. Find , the cycle-space dimension, and every even edge set.)
Count the isolated vertex as a component.
Solution · Answer
There are vertices, edges and components. The dimension is . The four even sets are empty, either one of the two triangles, and their union. The isolated vertex belongs to the graph but contributes no edge.
Quick check
(Prove that no nonempty edge set contained in a forest can be even. Why is simply counting its edges insufficient?)
Look for a leaf of the selected subgraph.
Solution · Answer
A nonempty subgraph of a forest has a component with an edge. That component is a nontrivial tree and has a leaf of degree one in the selected subgraph, so the edge set is not even. The number of edges alone does not determine the degrees: two sets with the same size can have different degree parities.
Quick check
(Let be any vertex set and an even edge set. If contains exactly three edges of , what can be concluded?)
Compare with the cut-parity theorem.
Solution · Answer
Such an even set cannot exist: the cut-parity theorem requires an even number of crossing selected edges, whereas three is odd. This conclusion uses selected edges, not the total number of edges in the cut.