# Bicycles and spanning trees of graphs

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the graph.

A cycle in a graph (note: not quite usual definition) is a set of edges such that every vertex is incident with an even number of the edges, and a cocycle in a graph is a set of edges that forms an edge cutset. A bicycle is a set of edges that is simultaneously a cycle and a cocycle.

These concepts are best thought of in terms of the vector space $$V = GF(2)^{E(G)}$$ where a set of edges is identified with the support of a vector in $$V$$; if $$B$$ is the vertex-edge incidence matrix of the graph $$G$$ then the cocycles are all the vectors in the row-space of $$B$$, while the cycles are all the vectors in the dual of the row-space of $$B$$ and the bicycles are the vectors in the intersection of these subspaces.

Therefore a graph always has $$2^b$$ bicycles for some $$b = b(G)$$ (and, for those who are interested, this number $$2^b$$ is given by $$\pm T(-1,-1)$$ where $$T$$ is the Tutte polynomial of $$G$$).

If the number of spanning trees of a graph is odd, then it has no non-zero bicycles and $$b=0$$. More generally it has been known for a long time that the number of bicycles is a divisor of the number of spanning trees of $$G$$. All the proofs that I know of this fact are algebraic and based on messing around with a matrix or something essentially equivalent.

Question: Is there a combinatorial interpretation or combinatorial proof of the fact that the number of spanning trees in a graph is a multiple of $$2^{b(G)}$$?

For example, if we could clump the spanning trees together into sets of size $$2^{b(G)}$$ by using the bicycles somehow.

Sub-question: Is there any interpretation of the quotient (i.e. number of spanning trees divided by $$2^{b(G)}$$)?

• So the bicycle space is the hull of the cycle space. Is there a standard basis for the bicycle space analogous to a set of fundamental cycles for the cycle space? Btw, the cocycle space is not all edge-cutsets but only the sets of edges which cross some cut. May 18, 2012 at 9:34
• Yes, you are right about the edge-cuts. As for a standard basis, there is one for plane graphs given by Shank's theory of "left-right paths" - walk around the edges of the graph turning alternately left and right at each vertex until you come back to the beginning, forming a closed trail. Edges traversed in only one direction in this trail form a bicycle. Repeat until every edge has been traversed once in each direction. The resulting set of bicycles then covers every bicycle-edge exactly twice, and is therefore not linearly independent, but throw any one out and you get a basis. May 19, 2012 at 6:25
• This doesn't answer the question, but re the sentence "If the number of spanning trees is odd then $b=0$": this is actually if and only if. See e.g. my unpublished paper from 1996, ics.uci.edu/~eppstein/pubs/Epp-TR-96-14.pdf. Sep 30, 2015 at 20:43