GATE CSE Discrete Mathematics PYQs & Answers — Page 2

Home
GATE
Computer Science and Information Technology
Topics
Discrete Mathematics

Questions 11–20 of 35. Imported answers require independent review unless marked reviewed.

Topic practice 35 questionsPage 2 of 4

Let

be the adjacency matrix of a simple undirected graph

. Suppose

is its own inverse. Which one of the following statements is always TRUE?

Your answerChoose one option.

is a cycle

is a perfect matching

is a complete graph

There is no such graph

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

and

be non-empty finite sets such that there exist one-to-one and onto functions (i) from

and (ii) from

. The number of possible values of

is __________

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is __________

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be the partial order defined on the set

as follows

The number of total orders on

that contain

is ________

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The chromatic number of a graph is the minimum number of colours used in a proper coloring of the graph. Let

be any graph with

vertices and chromatic number

. Which of the following statements is/are always TRUE?

Your answerSelect all correct options. You can choose more than one.

contains a complete subgraph with

vertices

contains an independent set of size at least

contains at least

edges

contains a vertex of degree at least

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the operators ◊ and □ defined by

, for positive integers. Which of the following statements is/are TRUE?

Your answerSelect all correct options. You can choose more than one.

Operator ◊ obeys the associative law

Operator □ obeys the associative law

Operator ◊ over the operator □ obeys the distributive law

Operator □ over the operator ◊ obeys the distributive law

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ________

Diagram for Computer Science and Information Technology question 60

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let

be the group of integers

with addition modulo

as the group operation. The number of elements in the group

that are their own inverses is ________

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Let p and q be two propositions. Consider the following two formulae in propositional logic.

S₁ : (¬p ∧ (p ∨ q)) → q

S₂ : q → (¬p ∧ (p ∨ q))

Which one of the following choices is correct?

Your answerChoose one option.

Both S₁ and S₂ are tautologies.

S₁ is a tautology but S₂ is not a tautology.

S₁ is not a tautology but S₂ is a tautology.

Neither S₁ nor S₂ is a tautology.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following sets, where

: Set of all

matrices with entries from the set

: Set of all functions from the set

to the set

Which of the following choice(s) is/are correct?

Your answerSelect all correct options. You can choose more than one.

There does not exist a bijection from

There exists a surjection from

There exists a bijection from

There does not exist an injection from

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

GATE CSE Discrete Mathematics PYQs

Question 17

Question 32

Question 34

Question 34

Question 51

Question 52

Question 60

Question 63

Question 7

Question 11