GATE CSE 2008 | Graph Theory Question 51 | Discrete Mathematics

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

$$G$$ is a graph on $$n$$ vertices and $$2n-2$$ edges. The edges of $$G$$ can be partitioned into two edge-disjoint spanning trees. Which of the following in NOT true for $$G$$?

For every subset of $$k$$ vertices, the induced subgraph has at most $$2k-2$$ edges

The minimum cut in $$G$$ has at least two edges

There are two edge-disjoint paths between every pair of vertices

There are two vertex-disjoint paths between every pair of vertices

GATE CSE 2008

MCQ (Single Correct Answer)

-0.6

Which of the following statements is true for every planar graph on $$n$$ vertices?

The graph is connected

The graph is Eulerian

The graph has a vertex-cover of size at most $$3n/4$$

The graph has an independent set of size at least $$n/3$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Let Graph$$(x)$$ be a predicate which denotes that $$x$$ is a graph. Let Connected$$(x)$$ be a predicate which denotes that $$x$$ is connected. Which of the following first order logic sentences DOES NOT represent the statement: $$Not\,\,\,every\,\,\,graph\,\,\,is\,\,\,connected?$$

$$\neg \forall x\left( {Graph\left( x \right) \Rightarrow Connected\left( x \right)} \right)$$

$$\exists x\left( {Graph\left( x \right) \wedge \neg Connected\left( x \right)} \right)$$

$$\neg \forall x\left( {\neg Graph\left( x \right) \vee Connected\left( x \right)} \right)$$

$$\forall x\left( {Graph\left( x \right) \Rightarrow \neg Connected\left( x \right)} \right)$$

GATE CSE 2007

MCQ (Single Correct Answer)

-0.6

Which of the following graphs has an Eulerian circuit?

Any $$k$$-regular graph where $$k$$ is an even number.

A complete graph on 90 vertices.

The complement of a cycle on 25 vertices.

None of the above.