Question

Consider a complete graph 𝐾𝑛 with 𝑛 vertices (𝑛> 4). Note that multiple spanning
trees can be constructed over 𝐾𝑛. 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 𝐾𝑛 ?

• A. 1 𝑛
• B. 1 2𝑛−3
• C. 0
• D. 1 𝑛−1

Hint:

Two spanning trees can be completely edge-disjoint since \(K_n\) splits into \(\lfloor n/2 \rfloor \geq 2\) edge-disjoint spanning trees for \(n > 4\), so the minimum intersection is 0, giving Jaccard coefficient 0.

Answer 1

The Correct Option is C

Step 1: A spanning tree of \(K_n\) has exactly \(n-1\) edges, since it must connect all \(n\) vertices without forming a cycle.
Step 2: The Jaccard coefficient between two edge sets \(T_1\) and \(T_2\) is \(\frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}\). Since \(|T_1 \cap T_2| \geq 0\) always, the coefficient can only be as low as \(0\), and this lower bound is achieved when \(T_1\) and \(T_2\) share no common edge at all.
Step 3: The question reduces to: can we always find two edge-disjoint spanning trees in \(K_n\) when \(n > 4\)? By the Nash-Williams / Tutte arboricity result, \(K_n\) can be decomposed into \(\lfloor n/2 \rfloor\) edge-disjoint spanning trees. For \(n > 4\), \(\lfloor n/2 \rfloor \geq 2\), so at least two completely edge-disjoint spanning trees always exist.
Step 4: Example for \(n=5\): edges of \(K_5\) are 12,13,14,15,23,24,25,34,35,45. Take \(T_1 = \{12,23,34,45\}\) (a path) and \(T_2 = \{13,14,15,24\}\) (a tree rooted at vertex 1 with an extra branch to vertex 2 via 4). Both are valid spanning trees, and they share no edge.
Step 5: Hence \(|T_1 \cap T_2| = 0\), so the Jaccard coefficient \(= \frac{0}{|T_1 \cup T_2|} = 0\), which is the lowest possible value.
Final Answer: \(\boxed{0}\)