GATE CSE 2006 | Graph Theory Question 64 | Discrete Mathematics

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the undirected graph $$G$$ defined as follows. The vertices of $$G$$ are bit strings of length $$n$$. We have an edge between vertex $$u$$ and vertex $$v$$ if and only if $$u$$ and $$v$$ differ in exactly one bit position (in other words, $$v$$ can be obtained from $$u$$ by flipping a single bit). The ratio of the choromatic number of $$G$$ to the diameter of $$G$$ is

$$1/{2^{n - 1}}$$

$$1/n$$

$$2/n$$

$$3/n$$

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 28 English

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}} $$