Skip to content
GATEiit

GATE CSE 2026 Session 2 Q36: Lowest Jaccard coefficient between two spanning trees of Kn

Question

Consider a complete graph KnK_n with nn vertices (n>4)(n > 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?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2026 final answer key)

Concept used: The Jaccard coefficient is 0 exactly when two spanning trees share no edge.

First step: KnK_n has n(n−1)/2≥2(n−1)n(n-1)/2 \ge 2(n-1) edges for n>4n > 4; try to build two edge-disjoint spanning trees (for example two different Hamiltonian paths).

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Engineering Mathematics PYQs

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2026 Session 2 questions →