Question

Consider a complete graph \(K_n\) with \(n\) vertices (\(n>4\)). Note that multiple spanning trees can be constructed over \(K_n\). Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.

Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of \(K_n\)?

• A. \(\dfrac{1}{n}\)
• B. \(\dfrac{1}{2n-3}\)
• C. \(0\)
• D. \(\dfrac{1}{n-1}\)

Hint:

Two spanning trees of K_n can be completely edge disjoint, since the graph has far more edges than two spanning trees need together, so the smallest possible overlap is zero edges.

Answer 1

The Correct Option is C

Step 1: Recall what makes a spanning tree.
A spanning tree of $K_n$ touches every vertex using exactly $n-1$ edges and has no cycle. Two spanning trees can share anywhere from $0$ up to $n-2$ edges (they cannot share all $n-1$, since two distinct spanning trees cannot be identical).

Step 2: Express Jaccard in terms of shared edges.
Let $k$ be the number of edges the two trees have in common. The union then holds $2(n-1)-k$ distinct edges, so
$$ J=\frac{k}{2(n-1)-k} $$
This is an increasing function of $k$: a bigger overlap gives a bigger Jaccard value, a smaller overlap gives a smaller one. So the question really asks: what is the smallest possible overlap $k$ between two spanning trees of $K_n$?

Step 3: Count how many edges $K_n$ actually has.
$K_n$ has $\binom{n}{2}=\dfrac{n(n-1)}{2}$ edges available to build trees from. Two spanning trees use at most $2(n-1)$ edges between them if they share nothing.

Step 4: Compare the two counts for $n>4$.
$$ \frac{n(n-1)}{2}-2(n-1) = (n-1)\left(\frac{n}{2}-2\right) = (n-1)\cdot\frac{n-4}{2} $$
For $n>4$, both factors $(n-1)$ and $(n-4)$ are positive, so this difference is positive. That means $K_n$ has strictly more edges than two spanning trees would need, so there is no shortage of edges that would force an overlap.

Step 5: Use the known packing result for complete graphs.
A classical result on tree packing says $K_n$ can be split into several completely edge-disjoint spanning trees, in fact up to $\left\lfloor \dfrac{n}{2} \right\rfloor$ of them. Since only 2 of them need to be edge-disjoint here, and $\left\lfloor n/2 \right\rfloor \geq 2$ once $n \geq 4$, two fully disjoint spanning trees are guaranteed to exist.

Step 6: Set $k=0$ and compute Jaccard.
$$ J=\frac{0}{2(n-1)-0}=0 $$

Step 7: Compare against the other choices.
Options like $\dfrac1n$, $\dfrac{1}{2n-3}$ and $\dfrac{1}{n-1}$ all assume $k\geq1$, but we have just shown $k=0$ is reachable, so none of them can be the true lowest value.

Step 8: Conclude.
$$ \boxed{0} $$