GATE CS 2026 Set 2 Q.36: Graph Theory

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$ ?

$\frac{1}{n}$

$\frac{1}{2n - 3}$

$0$

$\frac{1}{n - 1}$

Official answer and solution

Official answer: C
From: Official GATE 2026 answer key

Solution

Check whether $K_n$ ( $n > 4$ ) contains two edge-disjoint spanning trees.

Every spanning tree of $K_n$ has $n - 1$ edges. For any $n \ge 4$ , the complete graph $K_n$ has $\binom{n}{2} = \frac{n(n-1)}{2} \ge 2(n-1)$ edges and can be decomposed into $\lfloor n/2 \rfloor \ge 2$ edge-disjoint spanning paths (Hamiltonian paths). Since two edge-disjoint spanning trees $T_1$ and $T_2$ exist in $K_n$ for all $n > 4$ , their intersection is empty ( $|T_1 \cap T_2| = 0$ ). Thus the minimum Jaccard coefficient is:

\frac{|T_1 \cap T_2|}{|T_1 \cup T_2|} = \frac{0}{2n - 2} = 0

Final answer

Option (C)

Common trap

Assuming any two spanning trees of $K_n$ must share at least one edge.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 36 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source