1
GATE CSE 2006
MCQ (Single Correct Answer)
+1
-0.3
If all the edge weights of an undirected graph are positive, then any subject of edges that connects all the vertices and has minimum total weight is a
A
Hamiltonian cycle
B
grid
C
hypercube
D
tree
2
GATE CSE 2005
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be the simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of $$G$$ is 8. Then, the size of the maximum independent set of $$G$$ is:
A
12
B
8
C
Less than 8
D
More than 12
3
GATE CSE 2005
MCQ (Single Correct Answer)
+1
-0.3
Let $$G$$ be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
A
6
B
8
C
9
D
13
4
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
What is the maximum number of edges in an acyclic undirected graph with $$n$$ vertices?
A
$$n-1$$
B
$$n$$
C
$$n + 1$$
D
$$2n-2$$
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP