1
GATE CSE 2010
+2
-0.6
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph?
$${\rm I}.$$$$\,\,\,\,\,7,6,5,4,4,3,2,1$$
$${\rm I}{\rm I}.$$$$\,\,\,\,\,6,6,6,6,3,3,2,2$$
$${\rm I}{\rm I}{\rm I}.$$$$\,\,\,\,\,7,6,6,4,4,3,2,2$$
$${\rm I}V.$$$$\,\,\,\,\,8,7,7,6,4,2,1,1$$
A
$${\rm I}$$ and $${\rm I}$$$${\rm I}$$
B
$${\rm I}$$$${\rm I}$$$${\rm I}$$ and $${\rm I}$$$$V$$
C
$${\rm I}$$$$V$$ only
D
$${\rm I}$$$${\rm I}$$ and $${\rm I}$$$$V$$
2
GATE CSE 2008
+2
-0.6
Which of the following statements is true for every planar graph on $$n$$ vertices?
A
The graph is connected
B
The graph is Eulerian
C
The graph has a vertex-cover of size at most $$3n/4$$
D
The graph has an independent set of size at least $$n/3$$
3
GATE CSE 2008
+2
-0.6
$$G$$ is a simple undirected graph. Some vertices of $$G$$ are of odd degree. Add a node $$v$$ to $$G$$ and make it adjacent to each odd degree vertex of $$G$$. The resultant graph is sure to be
A
Regular
B
Complete
C
Hamiltonian
D
Euler
4
GATE CSE 2008
+2
-0.6
$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?
A
For every subset of $$k$$ vertices, the induced subgraph has at most $$2k-2$$ edges
B
The minimum cut in $$G$$ has at least two edges
C
There are two edge-disjoint paths between every pair of vertices
D
There are two vertex-disjoint paths between every pair of vertices
GATE CSE Subjects
EXAM MAP
Medical
NEET