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

Suppose I have a connected graph $G$ and a fixed edge $e = \langle u, v \rangle \in G$, and I want to count the number of spanning trees that involve $e$. I really only want to estimate the fraction of spanning trees containing $e$ compared to the total number of spanning trees $G$, that is, I want to find a lower bound $c \leq \kappa(G \backslash e) / \kappa(G)$

This lower bound should be in terms of the degrees of vertices $u,v$. Let $c(d,d')$ be the smallest possible value of $\kappa(G \backslash e) / \kappa(G)$ when the vertices have degree $d, d'$. What can one say about $c(d,d')$?

For example, if $d = 1$ or $d' = 1$, then $c(d,d') = 1$. (The edge must be part of a spanning tree of $G$.).

If $d = 2$, then $c(d,d') \geq 1/2$, as every spanning tree must involve one of the two edges incident on $u$, and the spanning trees using only $e$ are in bijection with the spanning trees using the other edge.

If $d = d' = 2$, then $c(d,d') \geq 2/3$; and so on.

Is there are general formula for $c(d,d')$?

share|improve this question
1  
Might be helpful: start with the matrix-tree theorem (en.wikipedia.org/wiki/Kirchhoff's_theorem) and replace the entries corresponding to the edge you're interested in with a parameter $t$. You get a polynomial in $t$ (it should be quadratic if you delete the row and column in which $t$ appears off the diagonal) and you want to estimate the ratio between its value at $0$ and its value at $1$. –  Qiaochu Yuan Nov 18 '11 at 16:08
    
The answer is highly dependent on the graph. Imagine uv being the only edge between two components of the graph. One can substitute other gadgets for an edge to reduce the fraction at will, which will remain largely independent of degree. Gerhard "Ask Me About System Design" Paseman, 2011.11.18 –  Gerhard Paseman Nov 18 '11 at 20:00
    
Gerhard -- I am asking for a lower bound over all possible graphs. –  David Harris Nov 18 '11 at 20:02
    
Doesn't $G\backslash e$ usually denote the graph $G$ with edge $e$ deleted? If so, then $\kappa(G \backslash e)$ is counting the number of spanning trees of $G$ that don't involve $e$. –  Barry Cipra Nov 18 '11 at 20:04
1  
@David: I think $G/e$ is standard for contraction, while $G\setminus e$ and $G-e$ are standard for deletion. –  Andreas Blass Nov 18 '11 at 21:05

3 Answers 3

up vote 14 down vote accepted

The probability that an edge $e=(u,v)$ is part of a uniform spanning tree is equal to the resistance between $u$ and $v$ when the graph is considered as an electric network (see the book by Lyons with Peres, section 4.2). The bounds you get (in term of the degrees $d_u,d_v$) are

$$ \frac{1}{\min(d_u,d_v)} \le R_{eff}(u \leftrightarrow v) \le 1$$

when you allow multiple edges, or

$$ \frac{(d_u-1)+(d_v-1)}{(d_u-1)+(d_v-1)+(d_u-1)(d_v-1)} < R_{eff}(u \leftrightarrow v) \le 1$$

when the graph is simple, and these bounds are sharp.

share|improve this answer

First of all, I think it's important to note that the number of spanning trees containing a given edge may depend on the global properties of a graph rather than just local properties like vertex degrees. For instance, if an edge is a cut-edge (also known as a bridge) then every spanning tree will contain it, but the vertex degrees won't necessarily tell you if that's the case.

To every graph $G$ we can associate a bivarite polynomial over $\mathbb{Z}$ called the Tutte polynomial $T_G(x,y)$. Any standard text on algebraic graph theory (e.g., Norman Biggs' Algebraic Graph Theory; Bela Bollobas' Modern Graph Theory, etc) will contain a treatment of it. The Tutte polynomial encodes a really surprising amount of combinatorial information about a graph, particularly regarding its connectivity and cycle structure. Among other things:

(1) $T_G(1,1)$ is equal to the number of spanning trees of $G$ (which is always positive, if $G$ is connected).

(2) If $e$ is any edge of $G$, then $T_{G}(x,y) = T_{G\e}(x,y) + T_{G*e}(x,y)$. $G\e$ is, as in your notation, $G$ with $e$ excised and $G*e$ is the graph obtained by merging the two vertices of $e$ together (and keeping any loops that form). With some base conditions, this is often taken as the definition of $T_G$.

Notice that $1 - T_{G*e}(1,1)/T_G(1,1) = T_{G-e}(1,1)/T_G(1,1)$. If I understand your problem correctly, you're interested in a choice of $e$ that minimizes the right hand side. So it might be helpful to consider maximizing the quotient on the left hand side, but both seem pretty opaque to me. Also I should warn you that Tutte polynomial computations, as you might expect, are NP-hard in general.

Hopefully this is of some use.

share|improve this answer

The assertion below regarding O(1/n) is in contradiction with another posted answer, so I leave the construction available while I check the assertion.

Let M_n be the (graph of the Hasse diagram of the) modular lattice on (n+2) elements. This will have 2n edges. Add two more edges on either side. Call the leaves u and v, and let us add an edge (the problem edge, called e) between u and v. I have a u-v gadget with 2n+3 edges on n+4 vertices, and n-many cycles of length 5. However, u and v have degree 2.

Now to the u side of this gadget, add an edge and then dangle whatever favorite nonempty graph off this edge, and choose a disjoint graph to dangle off of v. In this graph, u and v have degree 3. However, any spanning tree that contains e can be modified to one of at least some number of other spanning trees; the analysis is more complicated than I originally imagined, but I think one can use this to show the ratio for this edge is at most O(1/n). So if d and d' are at least 3, I see no useful lower bound for the fraction in terms of the degrees themselves regarding edge e.

Gerhard "Ask Me About System Design" Paseman, 2011.11.18

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.