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
Most viewed 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
1
answer
1
relation
Number of relations $S$ over set $\{0,1,2,3 \}$ such that $(x,y) \in S \Rightarrow x = y$
asked
Dec 27, 2017
in
Set Theory & Algebra
by
Lakshman Patel RJIT
Boss
(
36.3k
points)

41.7k
views
relations
+19
votes
2
answers
2
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
asked
Oct 24, 2014
in
Set Theory & Algebra
by
shree
Active
(
3.5k
points)

13.6k
views
settheory&algebra
+60
votes
6
answers
3
GATE201238
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
asked
Sep 12, 2014
in
Graph Theory
by
gatecse
Boss
(
18.4k
points)

9.3k
views
gate2012
graphtheory
normal
markstoall
counting
+29
votes
7
answers
4
GATE19941.6, ISRO200829
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
asked
Oct 4, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

8.8k
views
gate1994
graphtheory
permutationsandcombinations
normal
isro2008
counting
+34
votes
10
answers
5
GATE2016126
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

8.4k
views
gate20161
permutationsandcombinations
generatingfunctions
normal
numericalanswers
+28
votes
9
answers
6
GATE2015240
The number of onto functions (surjective functions) from set $X = \{1, 2, 3, 4\}$ to set $Y=\{a,b,c\}$ is ______.
asked
Feb 13, 2015
in
Set Theory & Algebra
by
jothee
Veteran
(
116k
points)

7.3k
views
gate20152
settheory&algebra
functions
normal
numericalanswers
+20
votes
10
answers
7
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
+27
votes
4
answers
8
GATE19976.3
The number of equivalence relations of the set $\{1,2,3,4\}$ is $15$ $16$ $24$ $4$
asked
Sep 29, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.8k
points)

7.1k
views
gate1997
settheory&algebra
relations
normal
+2
votes
3
answers
9
Reflexive ,symmetric relation
How many relations are reflexive or symmetric on set of n element?
asked
Jul 10, 2016
in
Combinatory
by
Anjali_aspirant
Active
(
1k
points)

7.1k
views
relations
+52
votes
7
answers
10
GATE2014151
Consider an undirected graph $G$ where selfloops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $ac \leq 1$ and $bd \leq 1$. The number of edges in this graph is______.
asked
Sep 28, 2014
in
Graph Theory
by
jothee
Veteran
(
116k
points)

6.9k
views
gate20141
graphtheory
numericalanswers
normal
graphconnectivity
+46
votes
7
answers
11
GATE2015139
Consider the operations $\textit{f (X, Y, Z) = X'YZ + XY' + Y'Z'}$ and $\textit{g (X, Y, Z) = X'YZ + X'YZ' + XY}$ Which one of the following is correct? Both $\left\{\textit{f} \right\}$ and $\left\{ \textit{g}\right\}$ are ... Only $\left\{ \textit{g}\right\}$ is functionally complete Neither $\left\{ \textit{f}\right\}$ nor $\left\{\textit{g}\right\}$ is functionally complete
asked
Feb 13, 2015
in
Set Theory & Algebra
by
makhdoom ghaya
Boss
(
41.2k
points)

6.9k
views
gate20151
settheory&algebra
functions
difficult
+35
votes
8
answers
12
GATE2016127
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
asked
Feb 12, 2016
in
Combinatory
by
Sandeep Singh
Loyal
(
7.8k
points)

6.9k
views
gate20161
permutationsandcombinations
recurrence
normal
numericalanswers
+48
votes
5
answers
13
GATE2016201
Consider the following expressions: $false$ $Q$ $true$ $P\vee Q$ $\neg Q\vee P$ The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ___________.
asked
Feb 12, 2016
in
Mathematical Logic
by
Akash Kanase
Boss
(
43.6k
points)

6.4k
views
gate20162
mathematicallogic
normal
numericalanswers
propositionallogic
+6
votes
8
answers
14
ISRO201473
How many different trees are there with four nodes $A, B, C$ and $D$? 30 60 90 120
asked
Sep 23, 2015
in
Combinatory
by
ajit
Active
(
3.3k
points)

6.1k
views
permutationsandcombinations
isro2014
+23
votes
6
answers
15
GATE2016229
The value of the expression $13^{99}\pmod{17}$ in the range $0$ to $16$, is ________.
asked
Feb 12, 2016
in
Combinatory
by
Akash Kanase
Boss
(
43.6k
points)

6.1k
views
gate20162
modulararithmetic
normal
numericalanswers
+2
votes
1
answer
16
Let a relation R be defined on the set of all real numbers by a R b <=> 1 + ab > 0 thus R is ?
asked
Nov 2, 2017
in
Set Theory & Algebra
by
techbrk3
Junior
(
585
points)

6k
views
+15
votes
3
answers
17
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
+51
votes
6
answers
18
GATE2016128
A function $f: \Bbb{N^+} \rightarrow \Bbb{N^+}$ , defined on the set of positive integers $\Bbb{N^+}$,satisfies the following properties: $f(n)=f(n/2)$ if $n$ is even $f(n)=f(n+5)$ if $n$ is odd Let $R=\{ i \mid \exists{j} : f(j)=i \}$ be the set of distinct values that $f$ takes. The maximum possible size of $R$ is ___________.
asked
Feb 12, 2016
in
Set Theory & Algebra
by
Sandeep Singh
Loyal
(
7.8k
points)

5.6k
views
gate20161
settheory&algebra
functions
normal
numericalanswers
+12
votes
7
answers
19
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
+3
votes
2
answers
20
How many transitive relations are there on a set with n elements if a)n=1 b) n=2 c) n=3
asked
Mar 7, 2017
in
Set Theory & Algebra
by
Sanjay Sharma
Veteran
(
50.7k
points)

5.5k
views
+43
votes
2
answers
21
GATE2015255
Which one of the following wellformed formulae is a tautology? $\forall x \, \exists y \, R(x,y) \, \leftrightarrow \, \exists y \, \forall x \, R(x, y)$ ... $\forall x \, \forall y \, P(x,y) \, \rightarrow \, \forall x \, \forall y \, P(y, x)$
asked
Feb 13, 2015
in
Mathematical Logic
by
jothee
Veteran
(
116k
points)

5.4k
views
gate20152
mathematicallogic
normal
firstorderlogic
+20
votes
5
answers
22
GATE20057
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be: $O(n)$ $O(n \log n)$ $O \left( n^{\frac{3}{2}} \right)$ $O\left(n^3\right)$
asked
Sep 22, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.8k
points)

5.4k
views
gate2005
settheory&algebra
normal
relations
+33
votes
6
answers
23
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
+25
votes
2
answers
24
GATE20021.25, ISRO200830, ISRO20166
The maximum number of edges in a nnode undirected graph without self loops is $n^2$ $\frac{n(n1)}{2}$ $n1$ $\frac{(n+1)(n)}{2}$
asked
Sep 16, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

5.3k
views
gate2002
graphtheory
easy
isro2008
isro2016
graphconnectivity
+33
votes
4
answers
25
GATE2016227
Which one of the following wellformed formulae in predicate calculus is NOT valid ? $(\forall _{x} p(x) \implies \forall _{x} q(x)) \implies (\exists _{x} \neg p(x) \vee \forall _{x} q(x))$ $(\exists x p(x) \vee \exists x q (x)) \implies \exists x (p(x) \vee q (x))$ ... $\forall x (p(x) \vee q(x)) \implies (\forall x p(x) \vee \forall x q(x))$
asked
Feb 12, 2016
in
Mathematical Logic
by
Akash Kanase
Boss
(
43.6k
points)

5.2k
views
gate20162
mathematicallogic
firstorderlogic
normal
+33
votes
6
answers
26
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
+21
votes
4
answers
27
GATE200721
How many different nonisomorphic Abelian groups of order $4$ are there? $2$ $3$ $4$ $5$
asked
Sep 22, 2014
in
Set Theory & Algebra
by
Kathleen
Veteran
(
59.8k
points)

4.9k
views
gate2007
groups
normal
+37
votes
5
answers
28
GATE200723
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
asked
Sep 22, 2014
in
Graph Theory
by
Kathleen
Veteran
(
59.8k
points)

4.9k
views
gate2007
graphtheory
normal
graphconnectivity
eulergraph
+16
votes
3
answers
29
GATE2015154
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
asked
Feb 14, 2015
in
Graph Theory
by
makhdoom ghaya
Boss
(
41.2k
points)

4.9k
views
gate20151
graphtheory
graphconnectivity
normal
graphplanarity
outofsyllabusnow
numericalanswers
+21
votes
5
answers
30
GATE2016203
The minimum number of colours that is sufficient to vertexcolour any planar graph is ________.
asked
Feb 12, 2016
in
Graph Theory
by
Akash Kanase
Boss
(
43.6k
points)

4.9k
views
gate20162
graphtheory
graphcoloring
normal
numericalanswers
Page:
1
2
3
4
5
6
...
174
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
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