GATE CSE 2014 Set 1 | Graph Theory Question 33 | Discrete Mathematics

GATE CSE 2014 Set 1

MCQ (Single Correct Answer)

-0.6

An ordered $$n$$-tuple $$\left( {{d_1},\,\,{d_2},\,....,{d_n}} \right)$$ with $${{d_1} \ge ,\,\,{d_2} \ge .... \ge {d_n}}$$ is called graphic if there exists a simple undirected graph with $$n$$ vertices having degrees $${d_1},{d_2},.....,{d_n}$$ respectively. Which of the following $$6$$- tuples is NOT graphic?

$$(1, 1, 1, 1, 1, 1)$$

$$(2, 2, 2, 2, 2, 2)$$

$$(3, 3, 3, 1, 0, 0)$$

$$(3, 2, 1, 1, 1, 0)$$

GATE CSE 2014 Set 1

Numerical

-0

Consider an undirectional graph $$G$$ where self-loops are not allowed. The vertex set of $$G$$ is $$\left\{ {\left( {i,j} \right):\,1 \le i \le 12,\,1 \le j \le 12} \right\}.$$ There is an edge between $$(a,b)$$ and $$(c,d)$$ if $$\left| {a - c} \right| \le 1$$ and $$\left| {b - d} \right| \le 1$$. The number of edges in this graph is _____.

Your input ____

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

-0.6

If $$G$$ is a forest with $$n$$ vertices and $$k$$ connected components, how many edges does $$G$$ have?

$$\left\lfloor {n/k} \right\rfloor $$

$$\left\lceil {n/k} \right\rceil \,$$

$$n - k$$

$$n - k + 1$$

GATE CSE 2014 Set 3

MCQ (Single Correct Answer)

-0.6

Let $$\delta $$ denote the minimum degree of a vertex in a graph. For all planar graphs on $$n$$ vertices with $$\delta \ge 3$$, which one of the following is TRUE?

In any planar embedding, the number of faces is at least $${n \over 2} + 2$$

In any planar embedding, the number of faces is less than $${n \over 2} + 2$$

There is a planar embedding in which the number of facess is less than $${n \over 2} + 2$$

There is a planar embedding in which the number of faces is at most $${n \over {\delta + 1}}$$

PREVIOUS NEXT