GATE CS 2026 (Afternoon) — Question 36

Discrete MathematicsGraph Theory (Connectivity, Paths, Cycles, Trees)MCQ2 marks · −2/3 if wrongHard

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 \)?
  1. A
    \( \frac{1}{n} \)
  2. B
    \( \frac{1}{2n - 3} \)
  3. C
    0
  4. D
    \( \frac{1}{n - 1} \)
Practise the full 2026-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAFree All-India Mock — every SundayA full GATE CS paper, exactly 180 minutes, ranked across India with your GATE score.
Practise more on Graph Theory (Connectivity, Paths, Cycles, Trees)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group