2
$\begingroup$

In graph theory, for a connected, undirected finite graph one can easily find a set of fundamental cycles - I understand that part. This forms a basis of some linear space of all cycles of that graph, meaning any such cycle is a linear combination of these fundamental cycles. What I don't understand is how one defines such linear space, and how to prove last statement. Can anyone direct me to a book or article which would explain this - if there is a simple way of spelling it out here, that would be even better.

$\endgroup$
1
  • $\begingroup$ You might be interested in Section $1.9$ of Diestel's Graph Theory (Fifth Edition). $\endgroup$
    – Hendrix
    Commented Dec 17, 2020 at 17:55

1 Answer 1

3
$\begingroup$

To define the cycle space, we first define the edge space of a graph $G$. This can be done in two equivalent ways:

  1. As the set of all spanning subgraphs of $G$ (including all vertices, though possibly with degree $0$). Two subgraphs $H_1, H_2$ can be "added" by taking the symmetric difference of their edge sets: the subgraph $H_1 \mathbin{\Delta} H_2$ has an edge iff exactly one of $H_1$ or $H_2$ had it.
  2. As the set of all functions from $E(G)$ to $\mathbb F_2$ (the field with two elements). This is a vector space over $\mathbb F_2$; scalar multiplication isn't very interesting over this field, and vector addition is just adding two functions pointwise.

Each cycle (together with all vertices not part of it, if necessary) gives us a spanning subgraph of $G$, so it's an element of the edge space. Thinking of it in the second way, given a cycle $C$, we can define its indicator function $f : E(G) \to \mathbb F_2$ by setting $f(e) = 1$ if $e$ is an edge of $C$, and $f(e)=0$ otherwise.

The set of all elements of the edge space which can be obtained by adding cycles is the cycle space. This has an alternate characterization: it is the set of all spanning subgraphs in which every vertex has even degree.


A cycle basis is a minimal set of cycles which generates the cycle space. The fundamental cycle basis is obtained from a spanning tree $T$ as follows: for each edge $e \notin E(T)$, we take the cycle $C_e$ by finding the unique path in $T$ between the endpoints of $e$, and then combining that with $e$ itself to create a cycle.

Your question is, as I understand it: why is the fundamental cycle basis a cycle basis?

Since it consists of cycles, it generates a subspace of the cycle space. It's linearly independent because each $C_e$ is the only element of the fundamental cycle space that includes edge $e$. (Linear independence here means that there's no nontrivial sum that adds to the zero function: no nontrivial symmetric difference that gives the empty graph. That's true here because the symmetric difference of distinct fundamental cycles $C_e \mathbin{\Delta} C_{e'} \mathbin{\Delta} C_{e''} \mathbin{\Delta} \cdots$ will include the edges $e, e', e'', \dots$: it won't be empty.)

The last thing we need from a basis is that it generates every element of the cycle space. So let $H$ be an element of the cycle space.

We begin by taking $$H \mathbin{\Delta} C_{e_1} \mathbin{\Delta} C_{e_2} \mathbin{\Delta} \cdots \mathbin{\Delta} C_{e_k}$$ where $e_1, e_2, \dots, e_k$ are all the edges of $H$ that are not in $T$. The resulting graph is still in the cycle space, because everything in this expression was. It is also a subgraph of $T$, because every edge $e_i \notin E(T)$ was deleted by taking the symmetric difference with $C_{e_i}$.

Any nontrivial element of the cycle space contains a cycle (start at any vertex with positive degree, and keep walking around until you get back to a vertex you've seen before - you can't get stuck because every vertex you visit has degree at least $2$). But this element of the cycle space can't contain a cycle: it's a subgraph of a tree! So it must be trivial, and therefore $$H = C_{e_1} \mathbin{\Delta} C_{e_2} \mathbin{\Delta} \cdots \mathbin{\Delta} C_{e_k}.$$ We've shown that any element of the cycle space can be expressed in terms of the fundamental cycle basis!

$\endgroup$
1
  • $\begingroup$ Thanks Misha, that's exactly what I needed! $\endgroup$
    – Honza
    Commented Dec 17, 2020 at 19:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .