Consider a complete graph 𝐾𝑛 with 𝑛 vertices (𝑛 > 4). Note that multiple…

PYQ GATE 2026

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

  1. A.

    1/n

  2. B.

    1/(2n-3)

  3. C.

    0

  4. D.

    1/(n-1)

Attempted by 157 students.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…