GATE CSE 2006 | Graphs Question 19 | Data Structures

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let T be a depth-first search tree in an undirected graph G. Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?

There must exist a vertex w adjacent to both u and v in G

There must exist a vertex w whose removal disconnects u and v in G

There must exist a cycle in G containing u and v

There must exist a cycle in G containing u and all its neighbors in G.

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

d(r, u) < d(r, v)

d(r, u) > d(r, v)

d(r, u)$$ \le $$d(r, v)

None of the above

GATE CSE 2001

MCQ (Single Correct Answer)

-0.6

How many undirected graphs (not necessarily connected) can be constructed out of a given set V = { v₁,v₂,........,v_n } of n vertices?

$$\frac{n(n-1)} {2}$$

2ⁿ

$$2^\frac{n(n-1)} {2}$$

GATE CSE 2000

MCQ (Single Correct Answer)

-0.6

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

{u, v} must be an edge in G, and u is a descendant of v in T

{u, v} must be an edge in G, and v is a descendant of u in T

If {u, v} is not an edge in G then u is a leaf in T

If {u, v} is not an edge in G then u and v must have the same parent in T