I'm going through the book 'Graph theory', written by Bondy and Murty. I'm currently trying to grasp the idea of bonds, but I find this a rather difficult concept. So my first question is if someone can suggest me another book/article that discusses this?
Furthermore, in exercise 2.6.5 one has to compute the number of elements of the bond or cycle space.
The vector space considered is $\mathcal{E}(G)$, a vector space of dimension $m$ (number of edges) over $GF(2)$. It's the set of all edges of the graph, with as operation symmetric difference. The cycle space $\mathcal{C}(G)$ consists of all even subgraphs, while the bond space $\mathcal{B}(G)$ is the set of all edge cuts.
I want to know the dimension $a$ of the bond (or cycle) space, to conclude that there are $2^a$ elements. Since I know that the bond and cycle space are orthogonal, I only have to know one of them.
The problem for me is that I cannot come up with a basis for the cycle space, since I don't know how to build cycles from other using the symmetric difference. Same problem for the bond space.
Is there another way to compute this number or can somebody help me out? :)
To "add" two cycles (=Eulerian subgraph in this context), think about placing them on top of each other and then deleting edges that appear twice. The result is still an Eulerian subgraph.
There is a standard way to write down bases for these spaces though. Here's a hint: Consider a spanning forest $F$.
If $e$ is an edge not in $F$, then $F\cup e$ contains a unique cycle. Are the collection of such cycles linearly independent? How many such cycles are there?
If $e=(v,w)$ is an edge that is in $F$, then removing $F$ increases the number of components of $F$ by $1$. So the edges in $G$ between these two components is a bond. Are these linearly independent? How many such bonds are there?
The answer to the above two questions, together with the fact that $\dim(\mathcal{C}(G))+\dim(\mathcal{B}(G))=m$ will tell you that in fact you have found bases for the respective subspaces.