18
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Brendan McKay
    Commented May 18, 2012 at 9:34
  • $\begingroup$ 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. $\endgroup$
    – Gordon Royle
    Commented May 19, 2012 at 6:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Sep 30, 2015 at 20:43
  • $\begingroup$ Can we call them bikes for short $\endgroup$
    – Akiva Weinberger
    Commented Jun 25 at 15:08

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This does not answer the question. It is well understood that the Tute polynomial determines the number of spanning trees. $\endgroup$
    – Chris Godsil
    Commented Sep 30, 2015 at 14:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .