The GATE Grind

GATE 2026 CS (CS2) – Question 36

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Consider a complete graph $K_n$ with $n>4$ vertices. Each spanning tree of $K_n$ is represented as a set of edges. The Jaccard coefficient between two sets is the ratio of the size of their intersection to the size of their union. Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of $K_n$?

  1. $\frac{1}{n}$
  2. $\frac{1}{2n-3}$
  3. 0
  4. $\frac{1}{n-1}$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) 0

Explanation

A spanning tree on $n$ vertices has $n-1$ edges. In a complete graph $K_n$ with $n\ge4$, it is possible to choose two edge-disjoint spanning trees. Then their intersection has size 0, and the Jaccard coefficient becomes $$\frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}=0.$$ Therefore, the minimum possible value is 0, so option (C) is correct.