cycle space in graph theory

2k Views Asked by At

I read the following definition of the cycle space in a set of notes.

Definition (Cycle space): Let $G=(V,E)$ . The cycle space of $G$ is an element of $2^{E}$ denoted $\mathcal{C}$ and is the smallest set (of sets) containing the $\emptyset$, all cycles in $G$ and (where each cycle is treated as a set of edges) and all unions of edge disjoint cycles in $G$.

Surely they made a mistake when they said $\mathcal{C}$ is an element of $2^{E}$? Surely they actually mean that $\mathcal{C} \subseteq 2^{E}$?

1

There are 1 best solutions below

0
On

Since to create a cycle you need a set of edges, therefore $\mathcal{C} \subseteq 2^{E}$. Further if your graph is planar the following should hold:

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.

from CylceSpace:Planar graphs,Homology. In this case $|\mathcal{C}| \leq 2^{|F|}$, where $F$ is the number of faces.