GATE CSE 2005 | Graph Theory Question 67 | Discrete Mathematics

PREVIOUS NEXT

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Which one of the following graphs is NOT planar? GATE CSE 2005 Discrete Mathematics - Graph Theory Question 29 English

GATE CSE 2004

MCQ (Single Correct Answer)

-0.6

Let $${G_1} = \left( {V,\,{E_1}} \right)$$ and $${G_2} = \left( {V,\,{E_2}} \right)$$ be connected graphs on the same vertex set $$V$$ with more than two vertices. If $${G_1} \cap {G_2} = \left( {V,{E_1} \cap {E_2}} \right)$$ is not a connected graph, then the graph $${G_1} \cup {G_2} = \left( {V,{E_1} \cup {E_2}} \right)$$

cannot have a cut vertex

must have a cycle

must have a cut-edge (bridge)

has chromatic number strictly greater than those of $${G_1}$$ and$${G_2}$$

GATE CSE 2004

MCQ (Single Correct Answer)

-0.6

What is the number of vertices in an undirected connected graph with $$27$$ edges, $$6$$ vertices of degree $$2$$, $$\,\,$$ $$3$$ vertices of degree 4 and remaining of degree 3?

$$10$$

$$11$$

$$18$$

$$19$$

GATE CSE 2004

MCQ (Single Correct Answer)

-0.6

How many graphs on $$n$$ labeled vertices exist which have at least $$\left( {{n^2} - 3n} \right)/2\,\,\,$$ edges?

$${}^{\left( {{n^ \wedge }2 - n} \right)/2}{C_{\left( {{n^ \wedge }2 - 3n} \right)/2}}$$

$${\sum\limits_{k = 0}^{\left( {{n^ \wedge }2 - 3n} \right)/2} {{}^{\left( {{n^ \wedge }2 - n} \right)}{C_k}} }$$

$${}^{\left( {{n^ \wedge }2 - n} \right)/2}{C_n}$$

$$\sum\nolimits_{k = 0}^n {{}^{\left( {{n^ \wedge }2 - n} \right)/2}{C_k}} $$