1
GATE CSE 2007
+2
-0.6
What is the largest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning trees?
A
1
B
2
C
3
D
n
2
GATE CSE 2006
+2
-0.6
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that
d(P) = 5 units      f(P) = 12 units
d(Q) = 6 units      f(Q) = 10 units
d(R) = 14 unit      f(R) = 18 units
Which one of the following statements is TRUE about the graph
A
There is only one connected component
B
There are two connected components, and P and R are connected
C
There are two connected components, and Q and R are connected
D
There are two connected components, and P and Q are connected
3
GATE CSE 2006
+2
-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?
A
There must exist a vertex w adjacent to both u and v in G
B
There must exist a vertex w whose removal disconnects u and v in G
C
There must exist a cycle in G containing u and v
D
There must exist a cycle in G containing u and all its neighbours in G.
4
GATE CSE 2006
+2
-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?
A
There must exist a vertex w adjacent to both u and v in G
B
There must exist a vertex w whose removal disconnects u and v in G
C
There must exist a cycle in G containing u and v
D
There must exist a cycle in G containing u and all its neighbors in G.
GATE CSE Subjects
Theory of Computation
Operating Systems
Algorithms
Digital Logic
Database Management System
Data Structures
Computer Networks
Software Engineering
Compiler Design
Web Technologies
General Aptitude
Discrete Mathematics
Programming Languages
Computer Organization
EXAM MAP
Joint Entrance Examination