Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 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)}$)?

share|improve this question
    
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. –  Brendan McKay May 18 '12 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. –  Gordon Royle May 19 '12 at 6:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.