Take the 2-minute tour ×

Consider a minimally connected graph (i.e., a spanning tree) on $n$ nodes, $\mathcal{T}=(\mathcal{V},\mathcal{E}_{\tau})$,

and its complement $\overline{\mathcal{T}}=(\mathcal{V},\overline{\mathcal{E}}_{\tau})$.

That is, $\mathcal{T} \cup \overline{\mathcal{T}} = K_n$, the complete graph on $n$ nodes.

Consider an edge $e_i \in \overline{\mathcal{E}}_{\tau}$. Then when this edge is added to the spanning tree $\mathcal{T}$, it forms a cycle. Denote the length of this cycle as $l(e_i)$, and let $c(e_i)\subseteq \mathcal{E}_{\tau}$ be the set of edges in $\mathcal{T}$ that the cycle uses.

I would like to determine the probability that two edges $e_i,e_j \in \overline{\mathcal{E}}_{\tau}$ when added to $\mathcal{T}$ form cycles that share $k$ edges;i.e., $|c(e_i) \cap c(e_j)|=k$.

More generally, what is the probability that $|\cap_{i=1}^p c(e_i)|=k$ for $e_i \in \overline{\mathcal{E}}_{\tau}$.

I hope the statement of this problem is clear.

I have begun thinking about this, but have been stuck. Here is what I have.

Let $E(\mathcal{T})$ and $E(\overline{\mathcal{T}})$ be the incidence matrix of $\mathcal{T}$ and $\overline{\mathcal{T}}$ respectively. Then $$T = \left(E(\mathcal{T})^TE(\mathcal{T}) \right)^{-1} E(\mathcal{T})^TE(\overline{\mathcal{T}})$$ is a matrix such that its $i$th column describes which edges in $\mathcal{T}$ are used to create a cycle with the edge $e_i \in \overline{\mathcal{E}}_{\tau}$.

The matrix $TT^T$ then gives information about how many times edges $i$ and $j$ are used in the same cycle. That is $[TT^T]_{ij}$ is an integer number that says how many times $e_i,e_j \in \mathcal{E}_{\tau}$ are used in the same cycle.

Also, the element $[T^TT]_{ii}$ is the length of the cycle formed from

and $[T^TT]_{ij}$ is the number of edges two cycles share (with a plus/minus sign in there).

Furthermore, there are a total of $(n/2)(n-1)-(n-1)$ possible cycles to form.

I am not very good at combinatorics and am having problems putting the pieces together. Thanks in advance!

share|improve this question
Simple observation: the answer depends on the choice of the spanning tree. If the spanning tree consists of edges $[1,i]$ for $i=2,3,\ldots, n$ then the probabilities you want to compute are non-zero only for $k=0,1$. If the spanning tree consists of edges $[1,2], [2,3], \ldots, [n-2,n-1]$, then you get non-zero probabilities for all $k<n-1$. So what kind of answer would you like to get? –  Łukasz Grabowski Dec 2 '11 at 22:46
What is your probability space? Are you considering random tree or a fixed tree? Of course the answer depends very much on the tree structure. –  Brendan McKay Dec 2 '11 at 23:18
thanks for the replies. I agree, the solution is dependent on the choice of tree. I am wondering, however, how to find these probabilities if the tree is given and known in the problem. Furthermore, the matrix $T$ is also known. Maybe a better question is given the tree, if I select two edges from $\overline{\mathcal{E}_{\tau}}$ (say uniformly at random) , what is the expected number of edges they share. –  dan Dec 3 '11 at 9:01

2 Answers 2

For simplicity of notation assume that the tree is $3$-regular (apart from the boundary) and that in your question we assume that we are interested only in those pairs of edges whose ends are all different.

Let $a$ and $b$ be two vertices in $\mathcal T$, not in the boundary. Let $p$ be the path joining them. Taking $p$ out leaves $4$ connected components. Denote $\mathcal T_a^1, \mathcal T_a^2$ the connected comopnents which touch the vertex $a$ and similarly for $b$. Then the number of pairs of edges such that their cycles intersect each other precisely in $p$ is $$ F(p):=(|\mathcal T_a^1|\cdot |\mathcal T_b^1|\cdot|\mathcal T_a^2|\cdot |\mathcal T_b^2|)^2, $$ because either [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^1$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^2$] or [the first edge has ends in $\mathcal T_a^1$ and $\mathcal T_b^2$ and the second edge has ends in $\mathcal T_a^2$ and $\mathcal T_b^1$].

So to get the probability that the intersection is of length exactly $k$, you need to sum-up $F(p)$ over all paths $p$ of length $k$ which don't touch the boundary, and divide it by the number of all pairs of edges which is $\frac{1}{8}\cdot n(n-1)(n-2)(n-3)$ (because we assume the edges have disjoint ends.)

share|improve this answer

disclaimer: Please cast a careful eye over the definition of $L(k)$. I hope you can salvage enough from this to answer your question.

Let $\mathcal P$ be the set of all paths in $\mathcal T$, and define $f: \mathcal P \mapsto \overline{\mathcal{E}_T}$ as the map

$$ f((v_0,\ldots,v_{k-1}) ) = (v_0,v_{k-1}) $$

Choose any path $p \in \mathcal P$ of length $k$. Let $C(p)$ be the set of all paths in $\mathcal T$ containing $p$. Choose two elements $a,b \in C(p)$ there are edges $f(a),f(b)$ such that

$$|c(f(a)) \cap c(f(b))| \geq k$$

Conversely, note that if $|c(e_i) \cap c(e_j)| \geq k$ then both $c(e_i)$ and $c(e_j)$ share a common path in $\mathcal T$ of length not less than $k$.

Hence the number of edges which share a path of length $\geq k$ is

$$ L(k) = \sum_{p \in \mathcal P, |p| = k-1} C^{|C(p)|}_2 $$

To calculate the expected number of edges that are shared, observe that $k$ must be strictly less than the length of the longest path $l$ (Lukasz provided some examples). So $L(n-1) = \cdots = L(l) = 0$. Calculate $L(l-1), L(l-2), \ldots L(1)$. Then the expected shared number of edges is

$$ \sum_{k=1}^{l-1} k * \frac{L(k) - L(k+1)}{(n/2)(n-1) - (n-1)}$$

share|improve this answer
thanks Daniel...yes, I am not entirely sure about $L(k)$. What is $C_2$? –  dan Dec 4 '11 at 8:50
I mean "the number of ways $2$ objects can be chosen from $|C(p)|$". –  Daniel Mansfield Dec 4 '11 at 23:11

Your Answer


