GateAI
Graph Theory

GATE CSE 2026 Set 2 · Q36

MCQ2 marksEasy

Time

Consider a complete graph KnK_n with nn vertices (n>4n > 4). Note that multiple spanning trees can be constructed over KnK_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 KnK_n ?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: C) 0

Graph Theory

Let T1T_1 and T2T_2 be two spanning trees of the complete graph KnK_n.

The Jaccard coefficient between their edge sets is given by:

J(T1,T2)=∣T1∩T2∣∣T1∪T2∣J(T_1, T_2) = \frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}

Since each spanning tree on nn vertices contains exactly n−1n - 1 edges, two spanning trees T1T_1 and T2T_2 can be completely edge-disjoint if ∣T1∩T2∣=0|T_1 \cap T_2| = 0.

The total number of edges in KnK_n is n(n−1)2\frac{n(n - 1)}{2}. For two edge-disjoint spanning trees to exist, the graph must have at least:

2(n−1)≤n(n−1)2  ⟹  n≥42(n - 1) \le \frac{n(n - 1)}{2} \implies n \ge 4

Since it is given that n>4n > 4, KnK_n always contains two edge-disjoint spanning trees T1T_1 and T2T_2.

For two edge-disjoint spanning trees:

∣T1∩T2∣=0|T_1 \cap T_2| = 0
∣T1∪T2∣=2(n−1)>0|T_1 \cup T_2| = 2(n - 1) > 0

Thus, the lowest possible value of the Jaccard coefficient is:

J(T1,T2)=02(n−1)=0J(T_1, T_2) = \frac{0}{2(n - 1)} = 0

Hence, the correct option is (C).

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Graph Theory previous year question is Q36 of the GATE CSE 2026 Set 2 paper. Find more GATE CSE PYQs on Graph Theory in Engineering Mathematics, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Graph Theory PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Theory in GATE CSE

Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 6 of them are 2-mark MCQs like this one, and GATE CSE 2026 Set 2 has 2.

How GATE tests Graph Theory

More from GATE CSE 2026 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2026 Set 2 · Q36 · MCQ

Consider a complete graph Kn with n vertices (n > 4). Note that multiple spanning trees can be constructed over Kn. 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 Kn ?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.