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