Consider a complete graph πΎπ with π vertices (π > 4). Note that multipleβ¦
2026
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/n
- B.
1/(2n-3)
- C.
0
- D.
1/(n-1)
Attempted by 22 students.
Show answer & explanation
Correct answer: C
Step 1: A spanning tree of a complete graph K_n with n vertices contains exactly n-1 edges.
Step 2: The Jaccard coefficient between two sets of edges E1 and E2 is defined as |E1 β© E2| / |E1 βͺ E2|.
Step 3: To minimize the coefficient, we must minimize the intersection size |E1 β© E2|.
Step 4: For n > 4, the complete graph K_n contains at least two edge-disjoint spanning trees.
Step 5: If two spanning trees are edge-disjoint, their intersection size is zero. This results in a Jaccard coefficient of 0 / (2n - 2) = 0.
A video solution is available for this question β log in and enroll to watch it.