1
GATE CSE 2024 Set 2
MCQ (More than One Correct Answer)
+2
-0.66

Let $G$ be an undirected connected graph in which every edge has a positive integer weight. Suppose that every spanning tree in $G$ has even weight. Which of the following statements is/are TRUE for every such graph $G$?

A

All edges in $G$ have even weight

B

All edges in $G$ have even weight OR all edges in $G$ have odd weight

C

In each cycle $C$ in $G$, all edges in $C$ have even weight

D

In each cycle $C$ in $G$, either all edges in $C$ have even weight OR all edges in $C$ have odd weight

2
GATE CSE 2024 Set 2
Numerical
+2
-0.66

The number of distinct minimum-weight spanning trees of the following graph is ________

3
GATE CSE 2020
+2
-0.67
Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u, v) $$\in$$ V $$\times$$ V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is
A
$$\Theta \left( {\left| E \right| + \left| V \right|} \right)$$
B
$$\Theta \left( {\left| E \right|\left| V \right|} \right)$$
C
$$\Theta \left( {\left| E \right|\log \left| V \right|} \right)$$
D
$$\Theta \left( {\left| V \right|} \right)$$
4
GATE CSE 2020
Numerical
+2
-0.67
Consider a graph G = (V, E), where V = {v1, v2, ...., v100},
E = {(vi, vj) | 1 ≤ i < j ≤ 100}, and weight of the edge (vi, vj) is |i - j|. The weight of the minimum spanning tree of G is ______.