GATEverse Practice, past papers & mock tests
GATE 2027: 115 days Sign in Create account
GATE 2026 · CS2 - Afternoon
AlgorithmsGraph AlgorithmshardMCQ2 marks
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 ?
Save your progress

Related Algorithms PYQs

GATE 2026 · CS1 - Forenoon

Consider the following recurrence relations: for all n > 1, T1(n) = 4*T1(n/2) + T2(n), and T2(n) = 5*T2(n/4) + \(\Theta(\log_2 n)\…

GATE 2026 · CS1 - Forenoon

Let G(V,E) be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges…

GATE 2026 · CS1 - Forenoon

Let G(V,E) be a simple, undirected graph. A vertex cover of G is a subset V' subset of V such that for every (u,v) in E, u in V' o…

GATE 2026 · CS1 - Forenoon

Let G(V,E) be a simple, undirected, edge-weighted graph with unique edge weights. Which of the following statements about the mini…

GATE 2026 · CS1 - Forenoon

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V,E) as input, where d[v] …

GATE 2026 · CS1 - Forenoon

An undirected, unweighted, simple graph G(V,E) is said to be 2-colorable if there exists a function c: V → {0,1} such that for eve…