1
GATE CSE 2010
+1
-0.3
Let $$G$$ $$\,\,\,\,\, = \,\,\,\left( {V,\,\,\,\,\,E} \right)$$ be a graph. Define $$\xi \left( G \right) = \sum\limits_d {{i_d} \times } {\mkern 1mu} d,$$ where $${{i_d}}$$ is the number of vertices of degree $$d$$ in $$G$$. If $$S$$ and $$T$$ are two different trees with $$\xi \left( S \right) = \xi \left( T \right)$$, then
A
$$\left| S \right| = 2\left| T \right|$$
B
$$\left| S \right| = \left| T \right| - 1$$
C
$$\left| S \right| = \left| T \right|$$
D
$$\left| S \right| = \left| T \right| + 1$$
2
GATE CSE 2009
+1
-0.3
What is the chromatic number of an $$n$$-vertex simple connected graph which does not contain any odd length cycle? Assume $$n \ge 2$$.
A
$$2$$
B
$$3$$
C
$$n-1$$
D
$$n$$
3
GATE CSE 2009
+1
-0.3
Which one of the following is TRUE for any simple connected undirected graph with more than $$2$$ vertices?
A
No two vertices have the same degree.
B
At least two vertices have the same degree.
C
At least three vertices have the same degree.
D
AA vertices have the same degree.
4
GATE CSE 2008
+1
-0.3
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
A
5
B
4
C
3
D
2
GATE CSE Subjects
EXAM MAP
Medical
NEET