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

1 Answer 1

The number of spanning trees of a plane(ly embedded) graph can be obtained from the Tutte polynomial.

(Pardon the proof via knot theory: the Jones polynomial of an alternating knot diagram is a specialization of the Tutte polynomial of an associated plane graph, and the Jones polynomial evaluated at -1 gives the number of spanning trees.)

For non-plane graphs, it may be possible to use the Bollobas-Riordan-Tutte polynomial. See for example: "The Jones polynomial and graphs on surfaces" by Dasbach, David Futer, Kalfagianni, Lin, Stoltzfus.

Thus I would expect such a proof to lie entirely within calculations of the Tutte polynomial.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.