1
GATE CSE 2011
MCQ (Single Correct Answer)
+1
-0.3
$$K4$$ and $$Q3$$ are graphs with the following structures. GATE CSE 2011 Discrete Mathematics - Graph Theory Question 69 English

Which one of the following statements is TRUE in relation to these graphs?

A
$$K4$$ is planar while $$Q3$$ is not
B
Both $$K4$$ and $$Q3$$ are planar
C
$$Q3$$ is planar while $$K3$$ is not
D
Neither $$K4$$ nor $$Q3$$ is planar
2
GATE CSE 2010
MCQ (Single Correct Answer)
+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$$
3
GATE CSE 2009
MCQ (Single Correct Answer)
+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$$
4
GATE CSE 2009
MCQ (Single Correct Answer)
+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.
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP