The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Previous GATE Questions in Discrete Mathematics
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
Recent
Hot!
Most votes
Most answers
Most views
Featured
Previous GATE
+3
votes
2
answers
1
GATE20195
Let $U = \{1, 2, \dots , n\}$ Let $A=\{(x, X) \mid x \in X, X \subseteq U \}$. Consider the following two statements on $\mid A \mid$. $\mid A \mid = n2^{n1}$ $\mid A \mid = \Sigma_{k=1}^n k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE? Only I Only II Both I and II Neither I nor II
asked
Feb 7
in
Combinatory
by
Arjun
Veteran
(
400k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
permutationsandcombinations
+4
votes
4
answers
2
GATE201910
Let $G$ be an arbitrary group. Consider the following relations on $G$: $R_1: \forall a , b \in G, \: a R_1 b \text{ if and only if } \exists g \in G \text{ such that } a = g^{1}bg$ $R_2: \forall a , b \in G, \: a R_2 b \text{ if and only if } a= b^{1}$ Which of the above is/are equivalence relation/relations? $R_1$ and $R_2$ $R_1$ only $R_2$ only Neither $R_1$ nor $R_2$
asked
Feb 7
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

2.2k
views
gate2019
engineeringmathematics
discretemathematics
settheory&algebra
groups
+1
vote
7
answers
3
GATE201912
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n1)!$ $1$ $\frac{(n1)!}{2}$
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

2.7k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
+3
votes
5
answers
4
GATE201935
Consider the first order predicate formula $\varphi$: $\forall x [ ( \forall z \: z \mid x \Rightarrow (( z=x) \vee (z=1))) \rightarrow \exists w ( w > x) \wedge (\forall z \: z \mid w \Rightarrow ((w=z) \vee (z=1)))]$ Here $a \mid b$ ... Set of all positive integers $S3:$ Set of all integers Which of the above sets satisfy $\varphi$? S1 and S2 S1 and S3 S2 and S3 S1, S2 and S3
asked
Feb 7
in
Mathematical Logic
by
Arjun
Veteran
(
400k
points)

3.8k
views
gate2019
engineeringmathematics
discretemathematics
mathematicallogic
+1
vote
1
answer
5
GATE201938
Let $G$ be any connected, weighted, undirected graph. $G$ has a unique minimum spanning tree, if no two edges of $G$ have the same weight. $G$ has a unique minimum spanning tree, if, for every cut of $G$, there is a unique minimumweight edge crossing the cut. Which of the following statements is/are TRUE? I only II only Both I and II Neither I nor II
asked
Feb 7
in
Graph Theory
by
Arjun
Veteran
(
400k
points)

2.3k
views
gate2019
engineeringmathematics
discretemathematics
graphtheory
graphconnectivity
0
votes
2
answers
6
GATE2019
What is the total number of different Hamiltonian cycles for the complete graph of n vertices?
asked
Feb 3
in
Graph Theory
by
Atul Sharma 1
(
65
points)

728
views
0
votes
0
answers
7
First Order Logic: GATE200541 ( From gate Overflow volume 1)
Can the answer to this be "∀x ∃y (teacher (x) ∧ student (y) ∧ likes (y,x))" ?
asked
Sep 30, 2018
in
Mathematical Logic
by
rambo1987
(
27
points)

82
views
+2
votes
2
answers
8
GATE199810b
Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m < n$ and $R^m = R^n$.
asked
Aug 12, 2018
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

198
views
gate1998
descriptive
settheory&algebra
relations
+1
vote
1
answer
9
Problem in gate199810 part b 
Can someone help me in "part b" of this question https://gateoverflow.in/1724/gate199810 . I am still not able to understand why $R^0$ is considered here ? and what is $R^0 $? Is it Equality relation? Do we have to consider it in every question of this type ?
asked
May 22, 2018
in
Set Theory & Algebra
by
Soumya29
Boss
(
15.5k
points)

141
views
discretemathematics
settheory&algebra
relations
0
votes
1
answer
10
Self Doubt. Related to https://gateoverflow.in/94634/gate198813ii#c216658.
1. If the set $S$ is countably infinite, prove or disprove that if $f$ maps $S$ onto $S$ (i.e $f:S \rightarrow S$ is a surjective function), then $f$ is onetoone.
asked
May 14, 2018
in
Set Theory & Algebra
by
Soumya29
Boss
(
15.5k
points)

165
views
discretemathematics
settheory&algebra
functions
+20
votes
10
answers
11
GATE201846
The number of possible minheaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.4k
points)

7.2k
views
gate2018
permutationsandcombinations
numericalanswers
+12
votes
8
answers
12
GATE201830
Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between ... then $\mid ij \mid =1$. Which of the statements above must necessarily be true? I only II only Both I and II Neither I nor II
asked
Feb 14, 2018
in
Graph Theory
by
gatecse
Boss
(
18.4k
points)

4.7k
views
gate2018
graphtheory
graphsearch
normal
+19
votes
4
answers
13
GATE201827
Let $N$ be the set of natural numbers. Consider the following sets, $P:$ Set of Rational numbers (positive and negative) $Q:$ Set of functions from $\{0,1\}$ to $N$ $R:$ Set of functions from $N$ to $\{0, 1\}$ $S:$ Set of finite subsets of $N$ Which of the above sets are countable? $Q$ and $S$ only $P$ and $S$ only $P$ and $R$ only $P, Q$ and $S$ only
asked
Feb 14, 2018
in
Set Theory & Algebra
by
gatecse
Boss
(
18.4k
points)

4.2k
views
gate2018
settheory&algebra
countableset
normal
+15
votes
3
answers
14
GATE201828
Consider the firstorder logic sentence $\varphi \equiv \exists \: s \: \exists \: t \: \exists \: u \: \forall \: v \: \forall \: w \forall \: x \: \forall \: y \: \psi(s, t, u, v, w, x, y)$ ... than or equal to $3$ There exists no model of $\varphi$ with universe size of greater than $7$ Every model of $\varphi$ has a universe of size equal to $7$
asked
Feb 14, 2018
in
Mathematical Logic
by
gatecse
Boss
(
18.4k
points)

5.8k
views
gate2018
mathematicallogic
normal
firstorderlogic
+6
votes
4
answers
15
GATE201819
Let $G$ be a finite group on $84$ elements. The size of a largest possible proper subgroup of $G$ is _____
asked
Feb 14, 2018
in
Set Theory & Algebra
by
gatecse
Boss
(
18.4k
points)

3.2k
views
gate2018
groups
numericalanswers
+10
votes
4
answers
16
GATE201818
The chromatic number of the following graph is _____
asked
Feb 14, 2018
in
Graph Theory
by
gatecse
Boss
(
18.4k
points)

2.3k
views
graphtheory
graphcoloring
numericalanswers
gate2018
+12
votes
7
answers
17
GATE20181
Which one of the following is a closed form expression for the generating function of the sequence $\{a_n\}$, where $a_n = 2n +3 \text{ for all } n=0, 1, 2, \dots$? $\frac{3}{(1x)^2}$ $\frac{3x}{(1x)^2}$ $\frac{2x}{(1x)^2}$ $\frac{3x}{(1x)^2}$
asked
Feb 14, 2018
in
Combinatory
by
gatecse
Boss
(
18.4k
points)

5.5k
views
gate2018
generatingfunctions
normal
+2
votes
1
answer
18
gate2017 numerical ability
in a box 3 blue ,4 green and 3 red ball then the probability to choose two same color ball?
asked
Jan 19, 2018
in
Mathematical Logic
by
Chandrabhan Vishwa 1
Active
(
1k
points)

125
views
+2
votes
1
answer
19
GATE2017131
https://gateoverflow.in/118312/gate2017131 In the explanation of how 1st statement is true they have said that $\lambda$12 + $\lambda$22 <=50 How is this statement arrived at?
asked
Oct 25, 2017
in
Mathematical Logic
by
A_i_$_h
Boss
(
12.7k
points)

164
views
+2
votes
1
answer
20
GATE20012.15 GATE19941.6
How many undirected graphs are possible with n vertices if graphs are not necessarily connected if they are necessarily connected
asked
Oct 12, 2017
in
Graph Theory
by
rishi71662data4
Active
(
2.6k
points)

275
views
graphtheory
permutationsandcombinations
+4
votes
0
answers
21
#Gate2003
Consider the following logic program P A(x) < B(x, y), C(y) < B(x,x) Which of the following first order sentences is equivalent to P? Can anyone explain how it can be solved ?
[closed]
asked
Jun 29, 2017
in
Mathematical Logic
by
Syedarshadali
(
347
points)

384
views
discretemathematics
firstorderlogic
gate2003
+33
votes
6
answers
22
GATE2017102
Consider the firstorder logic sentence $F:\forall x(\exists yR(x,y))$. Assuming nonempty logical domains, which of the sentences below are implied by $F$? $\exists y(\exists xR(x,y))$ $\exists y(\forall xR(x,y))$ $\forall y(\exists xR(x,y))$ $¬\exists x(\forall y¬R(x,y))$ IV only I and IV only II only II and III only
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

5.1k
views
gate20171
mathematicallogic
firstorderlogic
+18
votes
5
answers
23
GATE2017101
The statement $\left ( ¬p \right ) \Rightarrow \left ( ¬q \right )$ is logically equivalent to which of the statements below? $p \Rightarrow q$ $q \Rightarrow p$ $\left ( ¬q \right ) \vee p$ $\left ( ¬p \right ) \vee q$ I only I and IV only II only II and III only
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

2.7k
views
gate20171
mathematicallogic
propositionallogic
easy
+21
votes
8
answers
24
GATE2017223
$G$ is an undirected graph with $n$ vertices and $25$ edges such that each vertex of $G$ has degree at least $3$. Then the maximum possible value of $n$ is _________ .
asked
Feb 14, 2017
in
Graph Theory
by
Madhav
Active
(
1.7k
points)

4.3k
views
gate20172
graphtheory
numericalanswers
degreeofgraph
+33
votes
6
answers
25
GATE2017247
If the ordinary generating function of a sequence $\big \{a_n\big \}_{n=0}^\infty$ is $\large \frac{1+z}{(1z)^3}$, then $a_3a_0$ is equal to ___________ .
asked
Feb 14, 2017
in
Combinatory
by
Arjun
Veteran
(
400k
points)

5.3k
views
gate20172
permutationsandcombinations
generatingfunctions
numericalanswers
normal
+11
votes
8
answers
26
GATE2017147
The number of integers between $1$ and $500$ (both inclusive) that are divisible by $3$ or $5$ or $7$ is ____________ .
asked
Feb 14, 2017
in
Set Theory & Algebra
by
Arjun
Veteran
(
400k
points)

3.4k
views
gate20171
settheory&algebra
normal
numericalanswers
sets
+24
votes
4
answers
27
GATE2017129
Let $p$, $q$ and $r$ be propositions and the expression $\left ( p\rightarrow q \right )\rightarrow r$ be a contradiction. Then, the expression $\left ( r\rightarrow p \right )\rightarrow q$ is a tautology a contradiction always TRUE when $p$ is FALSE always TRUE when $q$ is TRUE
asked
Feb 14, 2017
in
Mathematical Logic
by
Arjun
Veteran
(
400k
points)

2.9k
views
gate20171
mathematicallogic
propositionallogic
+18
votes
4
answers
28
GATE2017221
Consider the set $X=\{a, b, c, d, e\}$ under partial ordering $R=\{(a,a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e) \}$ The Hasse diagram of the partial order $(X, R)$ is shown below. The minimum number of ordered pairs that need to be added to $R$ to make $(X, R)$ a lattice is ______
asked
Feb 14, 2017
in
Set Theory & Algebra
by
khushtak
Loyal
(
7.7k
points)

3.5k
views
gate20172
discretemathematics
lattice
numericalanswers
normal
+21
votes
5
answers
29
GATE2017224
Consider the quadratic equation $x^213x+36=0$ with coefficients in a base $b$. The solutions of this equation in the same base $b$ are $x=5$ and $x=6$. Then $b$= _____
asked
Feb 14, 2017
in
Set Theory & Algebra
by
khushtak
Loyal
(
7.7k
points)

3.9k
views
gate20172
polynomials
numericalanswers
+19
votes
7
answers
30
GATE2017211
Let $p, q, r$ ... $(\neg p \wedge r) \vee (r \rightarrow (p \wedge q))$
asked
Feb 14, 2017
in
Mathematical Logic
by
khushtak
Loyal
(
7.7k
points)

3.4k
views
gate20172
mathematicallogic
propositionallogic
Page:
1
2
3
4
5
6
...
12
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
COAP Round 1 has started
MTECH (COUURSE WORK) AI INTERVIEW EXPERIENCE 2019
All categories
General Aptitude
1.7k
Engineering Mathematics
7.4k
Discrete Mathematics
5.2k
Mathematical Logic
2.1k
Set Theory & Algebra
1.4k
Combinatory
898
Graph Theory
801
Probability
989
Linear Algebra
686
Calculus
497
Digital Logic
2.9k
Programming & DS
4.9k
Algorithms
4.3k
Theory of Computation
6k
Compiler Design
2k
Operating System
4.2k
Databases
4.1k
CO & Architecture
3.4k
Computer Networks
4.2k
Non GATE
1.4k
Others
1.6k
Admissions
591
Exam Queries
643
Tier 1 Placement Questions
23
Job Queries
72
Projects
23
Follow @csegate
Previous GATE Questions in Discrete Mathematics
Recent Blog Comments
It was free when I gave them, maybe they made it...
The tests are there but it ain't free. Cost is...
They removed their tests recently, I think it'll...
how did you get Success gateway test series for...
49,721
questions
53,593
answers
185,825
comments
70,878
users