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: Write down the Jaccard coefficient formula for two spanning trees.
For two sets \(L\) and \(R\), the Jaccard coefficient is
\[ J(L,R)=\frac{|L\cap R|}{|L\cup R|} \]
Every spanning tree of \(K_n\) has exactly \(n-1\) edges, since a tree on \(n\) vertices always has \(n-1\) edges.

Step 2: Work out the union size for two different spanning trees.
If two spanning trees \(T_1\) and \(T_2\) share \(k\) common edges, then
\[ |T_1\cap T_2|=k, \qquad |T_1\cup T_2|=(n-1)+(n-1)-k=2(n-1)-k \]
So the Jaccard coefficient is
\[ J=\frac{k}{2(n-1)-k} \]
This is smallest when \(k\) is as small as possible, and it becomes \(0\) exactly when \(k=0\), that is, when the two spanning trees share no edge at all.

Step 3: Check whether two completely edge-disjoint spanning trees can exist in \(K_n\).
\(K_n\) has
\[ \frac{n(n-1)}{2} \]
edges in total. Two edge-disjoint spanning trees together need
\[ 2(n-1) \]
edges. For \(n>4\),
\[ \frac{n(n-1)}{2} \geq 2(n-1) \]
whenever \(n\geq4\), so there are always enough edges available.

Step 4: Confirm with a small example, \(n=5\).
Take the vertices \(1,2,3,4,5\). One spanning tree is the path
\[ T_1: 1\text{-}2,\ 2\text{-}3,\ 3\text{-}4,\ 4\text{-}5 \]
Another spanning tree, chosen to avoid every edge of \(T_1\), is
\[ T_2: 1\text{-}3,\ 3\text{-}5,\ 5\text{-}2,\ 2\text{-}4 \]
\(T_2\) is connected, has no cycle, and touches all 5 vertices, so it is a valid spanning tree, and it shares no edge with \(T_1\). This shows \(k=0\) is actually achievable, not just a theoretical bound.

Step 5: Conclude the lowest possible value.
Since two completely edge-disjoint spanning trees can always be found in \(K_n\) for \(n>4\) (this follows from tree packing results, and the total edge count is generous enough), the smallest possible Jaccard coefficient is
\[ J_{min}=\frac{0}{2(n-1)}=0 \]

Step 6: Rule out the other options.
\(\dfrac{1}{n}\), \(\dfrac{1}{2n-3}\), and \(\dfrac{1}{n-1}\) would all require the two trees to share at least one edge, but sharing edges is not forced. Since sharing zero edges is possible, these values are not the true minimum.

Step 7: Final answer.
\[ \boxed{0} \]
This corresponds to option (C).