GATE 2026 CS2 Q.36: solution and answer

Official answer: CSource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

1. Every spanning tree of $K_n$ has exactly $n-1$ edges (a spanning tree on $n$ vertices always has $n-1$ edges), so each spanning tree corresponds to an $(n-1)$-element subset of $K_n$'s edge set.

2. The Jaccard coefficient of two such edge sets $T_1,T_2$ is $\frac{|E(T_1)\cap E(T_2)|}{|E(T_1)\cup E(T_2)|}$, which is always $\ge 0$; it is minimized to exactly $0$ precisely when $T_1$ and $T_2$ share no edge at all, i.e. when the two spanning trees are edge-disjoint.

3. So the question reduces to: can $K_n$ (for $n>4$) always supply two pairwise edge-disjoint spanning trees? $K_n$ has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n(n-1)}{2}$ edges in total. Since each spanning tree needs $n-1$ of them, the number of pairwise edge-disjoint spanning trees that can possibly be packed into $K_n$ is at most $\lfloor \frac{n(n-1)/2}{n-1}\rfloor =\lfloor \frac{n}{2}\rfloor$.

4. This bound is a classical tight result for complete graphs: $K_n$ can always be decomposed into (or shown to contain) $\lfloor \frac{n}{2}\rfloor$ pairwise edge-disjoint spanning trees — the bound is attained, not merely an upper limit. This also follows from the Nash-Williams/Tutte spanning-tree-packing theorem, since in $K_n$ the trivial vertex partition (no merging) gives the binding constraint.

5. For $n>4$ (i.e. $n\ge 5$), $\lfloor \frac{n}{2}\rfloor \ge 2$, so at least 2 pairwise edge-disjoint spanning trees of $K_n$ always exist. Pick any such pair $T_1,T_2$.

6. For this pair, $|E(T_1)\cap E(T_2)|=0$, so their Jaccard coefficient equals $\frac{0}{2(n-1)}=0$.

7. Since the Jaccard coefficient can never be negative, and the value $0$ is shown to be attainable for every $n>4$, the lowest possible value of the Jaccard coefficient between any two spanning trees of $K_n$ is $0$ — option (C).