GATE CS 2026 Set 2 Q26 — Graphs: Connectivity, Matching, Colouring

To find the lowest possible value of the Jaccard coefficient between any two spanning trees of $K_n$, let us analyze the definition of the Jaccard coefficient.

Let $T_1$ and $T_2$ be two spanning trees of $K_n$. Each spanning tree has exactly $n-1$ edges. The Jaccard coefficient between their edge sets $E(T_1)$ and $E(T_2)$ is defined as:

Since the sizes of sets are non-negative, the minimum possible value of the Jaccard coefficient is $0$. This minimum is achieved if and only if there exist two spanning trees $T_1$ and $T_2$ that are completely edge-disjoint, meaning:

Existence of Edge-Disjoint Spanning Trees

According to the Tutte-Nash-Williams theorem, a complete graph $K_n$ contains exactly $\lfloor n/2 \rfloor$ edge-disjoint spanning trees.

Given that $n > 4$ (i.e., $n \ge 5$):

This guarantees that for any $n > 4$, $K_n$ contains at least $2$ edge-disjoint spanning trees. Let these two trees be $T_1$ and $T_2$. Since they share no edges:

• $|E(T_1) \cap E(T_2)| = 0$
• $|E(T_1) \cup E(T_2)| = 2(n-1)$

Thus, the Jaccard coefficient is:

Therefore, the lowest possible value for the Jaccard coefficient is 0.