The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions and answers in Discrete Mathematics
+18
votes
5
answers
1
GATE20022.17
The binary relation $S= \phi \text{(empty set)}$ on a set $A = \left \{ 1,2,3 \right \}$ is Neither reflexive nor symmetric Symmetric and reflexive Transitive and reflexive Transitive and symmetric
answered
16 hours
ago
in
Set Theory & Algebra
by
pritishc
(
57
points)

2.6k
views
gate2002
settheory&algebra
normal
relations
+1
vote
1
answer
2
Graph Coloring
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ? There is a condition that adjacent vertices should not be of the same color I am getting $1680$. Is it correct?
answered
2 days
ago
in
Graph Theory
by
Satbir
Boss
(
13.2k
points)

257
views
graphtheory
graphcoloring
permutationandcombination
0
votes
1
answer
3
Planar Graph
Can minimum degree of a planar graph be $5$? Give some example
answered
3 days
ago
in
Graph Theory
by
Satbir
Boss
(
13.2k
points)

219
views
graphtheory
graphplanarity
+20
votes
12
answers
4
GATE201846
The number of possible minheaps containing each value from $\{1,2,3,4,5,6,7\}$ exactly once is _______
answered
5 days
ago
in
Combinatory
by
Kuldeep Pal
Active
(
1.3k
points)

7.3k
views
gate2018
permutationandcombination
numericalanswers
+37
votes
11
answers
5
GATE201535
The number of $4$ digit numbers having their digits in nondecreasing order (from left to right) constructed by using the digits belonging to the set $\{1, 2, 3\}$ is ________.
answered
5 days
ago
in
Combinatory
by
Kuldeep Pal
Active
(
1.3k
points)

3.8k
views
gate20153
permutationandcombination
normal
numericalanswers
+23
votes
7
answers
6
GATE2004IT35
In how many ways can we distribute $5$ distinct balls, $B_1, B_2, \ldots, B_5$ in $5$ distinct cells, $C_1, C_2, \ldots, C_5$ such that Ball $B_i$ is not in cell $C_i$, $\forall i= 1,2,\ldots 5$ and each cell contains exactly one ball? $44$ $96$ $120$ $3125$
answered
5 days
ago
in
Combinatory
by
Kuldeep Pal
Active
(
1.3k
points)

2.5k
views
gate2004it
permutationandcombination
normal
ballsinbins
+9
votes
3
answers
7
GATE19982.4
In a room containing $28$ people, there are $18$ people who speak English, $15$, people who speak Hindi and $22$ people who speak Kannada. $9$ persons speak both English and Hindi, $11$ persons speak both Hindi and Kannada whereas $13$ persons speak both Kannada and English. How many speak all three languages? $9$ $8$ $7$ $6$
answered
5 days
ago
in
Set Theory & Algebra
by
Nithin2698
(
25
points)

1.1k
views
gate1998
settheory&algebra
easy
sets
+1
vote
2
answers
8
Model Question IISc CDS CS Written Test Sample question
Anand is preparing a pizza with 8 slices, and he has 10 toppings to put on the pizza. He can put only one topping on each slice but can use the same topping on zero or more slices. In how many unique ways can he prepare the slices so that the same topping is not used in adjacent slices?
answered
5 days
ago
in
Combinatory
by
Satbir
Boss
(
13.2k
points)

205
views
iisc
cds
+10
votes
4
answers
9
GATE19891iv
The transitive closure of the relation $\left\{(1, 2), (2, 3), (3, 4), (5, 4)\right\}$ on the set $\left\{1, 2, 3, 4, 5\right\}$ is ___________.
answered
6 days
ago
in
Set Theory & Algebra
by
mohan123
(
135
points)

679
views
gate1989
settheory&algebra
relations
descriptive
+19
votes
3
answers
10
TIFR2014A5
The rules for the University of Bombay fiveaside cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students? $23$ $91$ $60$ $49$ None of the above.
answered
Jun 17
in
Combinatory
by
Kuldeep Pal
Active
(
1.3k
points)

821
views
tifr2014
permutationandcombination
discretemathematics
normal
pigeonholeprinciple
+34
votes
7
answers
11
GATE2017247
If the ordinary generating function of a sequence $\left \{a_n\right \}_{n=0}^\infty$ is $\large \frac{1+z}{(1z)^3}$, then $a_3a_0$ is equal to ___________ .
answered
Jun 17
in
Combinatory
by
mohan123
(
135
points)

5.4k
views
gate20172
permutationandcombination
generatingfunctions
numericalanswers
normal
+13
votes
8
answers
12
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}$
answered
Jun 17
in
Combinatory
by
Kuldeep Pal
Active
(
1.3k
points)

5.7k
views
gate2018
generatingfunctions
normal
permutationandcombination
+2
votes
1
answer
13
GATE19994
Let $G$ be a finite group and $H$ be a subgroup of $G$. For $a \in G$, define $aH=\left\{ah \mid h \in H\right\}$. Show that $aH = bH.$ Show that for every pair of elements $a, b \in G$, either $aH = bH$ or $aH$ and $bH$ are disjoint. Use the above to argue that the order of $H$ must divide the order of $G.$
answered
Jun 16
in
Set Theory & Algebra
by
Satbir
Boss
(
13.2k
points)

476
views
gate1999
settheory&algebra
groups
normal
cosets
+8
votes
3
answers
14
TIFR2011B23
Suppose $(S_{1}, S_{2},\ldots,S_{m})$ is a finite collection of nonempty subsets of a universe $U.$ Note that the sets in this collection need not be distinct. Consider the following basic step to be performed on this sequence. While there exist sets $S_{i}$ and ... of a finite universe $U$ and a choice of $S_{i}$ and $S_{j}$ in each step such that the process does not terminate.
answered
Jun 16
in
Set Theory & Algebra
by
Arjun
Veteran
(
408k
points)

349
views
tifr2011
settheory&algebra
sets
+16
votes
3
answers
15
GATE199811
Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A $\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$ List the ordered pairs of the equivalence relations induced by $\Pi_1$. Draw the graph of the above equivalence relation ... $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.
answered
Jun 15
in
Set Theory & Algebra
by
Satbir
Boss
(
13.2k
points)

1.6k
views
gate1998
settheory&algebra
normal
partialorder
descriptive
+7
votes
1
answer
16
TIFR2018B10
For two $n$ bit strings $x,y \in\{0,1\}^{n},$ define $z=x\oplus y$ to be the bitwise XOR of the two strings (that is, if $x_{i},y_{i},z_{i}$ denote the $i^{th}$ bits of $x,y,z$ respectively, then $z_{i}=x_{i}+y_{i} \bmod 2$ ... The number of such linear functions for $n \geq 2$ is: $2^{n}$ $2^{n^{2}}$ $\large2^{\frac{n}{2}}$ $2^{4n}$ $2^{n^{2}+n}$
answered
Jun 14
in
Set Theory & Algebra
by
Arjun
Veteran
(
408k
points)

224
views
tifr2018
functions
+17
votes
3
answers
17
GATE19992.2
Two girls have picked $10$ roses, $15$ sunflowers and $15$ daffodils. What is the number of ways they can divide the flowers among themselves? $1638$ $2100$ $2640$ None of the above
answered
Jun 14
in
Combinatory
by
brucebayne
(
21
points)

3.6k
views
gate1999
permutationandcombination
normal
0
votes
1
answer
18
MadeEasy Test Series: Probability
How to get the idea that we have to use Binomial distribution or Hypergeometric Distribution. I know that if the probability is not changing(i.e with replacement) then we go Binomial otherwise Hypergeometric. But in question, it is not indicating ... So is there any by default approach that we have to use Binomial if nothing is a mention about a replacement.
answered
Jun 13
in
Mathematical Logic
by
vizzard110
(
39
points)

28
views
madeeasytestseries
probability
binomialdistribution
+1
vote
1
answer
19
Doubt
How many distinct unlabeled graphs are there with 4 vertices and 3 edges?
answered
Jun 13
in
Graph Theory
by
Gyanu
Active
(
1.5k
points)

65
views
0
votes
1
answer
20
Zeal Test Series 2019: Graph Theory  Graph Connectivity
answered
Jun 12
in
Graph Theory
by
Gyanu
Active
(
1.5k
points)

74
views
zeal
graphtheory
graphconnectivity
zeal2019
+2
votes
3
answers
21
Degree of vertices
Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true? Vertex $n$ has degree $1$ Graph is connected There is a path from vertex $1$ to vertex $n$ Spanning tree will include edge connecting vertex $1$ and vertex $n$
answered
Jun 12
in
Graph Theory
by
Sainath Mandavilli
(
23
points)

100
views
discretemathematics
graphtheory
0
votes
2
answers
22
ACE Workbook:
ACE Workbook: Q) Let G be a simple graph(connected) with minimum number of edges. If G has n vertices with degree1,2 vertices of degree 2, 4 vertices of degree 3 and 3 vertices of degree4, then value of n is ? Can anyone give the answer and how to approach these problems. Thanks in advance.
answered
Jun 12
in
Graph Theory
by
Akanksha Agrawal
(
33
points)

62
views
graphtheory
0
votes
2
answers
23
Self DoubtCombinatory
In how many ways we can put $n$ distinct balls in $k$ dintinct bins?? Will it be $n^{k}$ or $k^{n}$?? Taking example will be easy way to remove this doubt or some other ways possible??
answered
Jun 9
in
Combinatory
by
Koushik Sinha 2
(
253
points)

61
views
discretemathematics
permutationandcombination
+3
votes
5
answers
24
TIFR2019B13
A row of $10$ houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses? $199$ $683$ $1365$ $3^{10}2^{10}$ $3^{10}$
answered
Jun 8
in
Combinatory
by
shaktisingh
(
91
points)

280
views
tifr2019
engineeringmathematics
discretemathematics
permutationandcombination
+1
vote
2
answers
25
GATE199017c
Show that the elements of the lattice $(N, \leq)$, where $N$ is the set of positive intergers and $a \leq b$ if and only if $a$ divides $b$, satisfy the distributive property.
answered
Jun 8
in
Set Theory & Algebra
by
Arjun
Veteran
(
408k
points)

239
views
gate1990
descriptive
settheory&algebra
lattice
+3
votes
1
answer
26
TIFR2017B6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FOL
answered
Jun 8
in
Mathematical Logic
by
Arjun
Veteran
(
408k
points)

176
views
tifr2017
firstorderlogic
normal
0
votes
1
answer
27
TIFR2019B12
Let $G=(V,E)$ be a directed graph with $n(\geq 2)$ vertices, including a special vertex $r$. Each edge $e \in E$ has a strictly positive edge weight $w(e)$. An arborescence in $G$ rooted at $r$ is a subgraph $H$ of $G$ in which every ... $w^*$ is less than the weight of the minimum weight directed Hamiltonian cycle in $G$, when $G$ has a directed Hamiltonian cycle
answered
Jun 8
in
Graph Theory
by
Arjun
Veteran
(
408k
points)

240
views
tifr2019
graphconnectivity
graphtheory
difficult
0
votes
1
answer
28
UGCNETJuly2018II76
Consider the following statements: False $\models$ True If $\alpha \models (\beta \wedge \gamma \text{ then } \alpha \models \gamma$ Which of the following is correct with respect to above statements? Both statement a and statement b are false Statement a is true and statement b is false Statement a is false and statement b is true Both statement a and statement b are true
answered
Jun 8
in
Discrete Mathematics
by
Irfanshaan
(
11
points)

416
views
ugcnetjuly2018ii
discretemathematics
propositionallogic
+7
votes
1
answer
29
GATE19879e
How many true inclusion relations are there of the from $A \subseteq B$, where $A$ and $B$ are subsets of a set $S$ with $n$ elements?
answered
Jun 7
in
Set Theory & Algebra
by
Arjun
Veteran
(
408k
points)

436
views
gate1987
settheory&algebra
relations
0
votes
1
answer
30
ISI2017MMA26
Let $n$ be the number of ways in which 5 men and 7 women can stand in a queue such that all the women stand consecutively. Let $m$ be the number of ways in which the same 12 persons can stand in a queue such that exactly 6 women stand consecutively. Then the value of $\frac{m}{n}$ is $5$ $7$ $5/7$ $7/5$
answered
Jun 7
in
Combinatory
by
venkatesh pagadala
(
495
points)

27
views
isi2017
engineeringmathematics
discretemathematics
permutationandcombination
0
votes
1
answer
31
GATE198814i
Consider the following wellformed formula: $\exists x \forall y [ \neg \: \exists z [ p (y, z) \wedge p (z, y) ] \equiv p(x,y)]$ Express the above wellformed formula in clausal form.
answered
Jun 7
in
Mathematical Logic
by
Arjun
Veteran
(
408k
points)

145
views
gate1988
descriptive
firstorderlogic
clausalform
nongate
0
votes
1
answer
32
GATE199525b
Determine the number of positive integers $(\leq 720)$ which are not divisible by any of $2,3$ or $5.$
answered
Jun 6
in
Set Theory & Algebra
by
Arjun
Veteran
(
408k
points)

73
views
gate1995
settheory&algebra
numericalanswers
sets
+1
vote
2
answers
33
UGCNETDec2015II6
Which of the following arguments are not valid ? "If Gora gets the job and works hard, then he will be promoted. if Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard." "Either Puneet is not ... $n^2 > 1$, then $n>1$. a and c b and c a,b, and c a and b
answered
Jun 6
in
Mathematical Logic
by
Satbir
Boss
(
13.2k
points)

1.4k
views
ugcnetdec2015ii
discretemathematics
mathematicallogic
+2
votes
1
answer
34
GATE19879d
Specify an adjacencylists representation of the undirected graph given above.
answered
Jun 5
in
Graph Theory
by
Satbir
Boss
(
13.2k
points)

298
views
gate1987
graphtheory
easy
graphconnectivity
descriptive
0
votes
0
answers
35
#ACE ACADEMY BOOKLET QUESTION
The solution of $\sqrt{a_n} – 2\sqrt{a_{n1}} + \sqrt{a_{n2}} = 0$ where $a_0 = 1$ and $a_1 = 2$ is ${\Big[\frac{2^{n+1} + (1)^n}{3}\Big]}^2$ $(n+1)^2$ $(n1)^3$ $(n1)^2$
asked
Jun 5
in
Combinatory
by
`JEET
Active
(
3.3k
points)

67
views
discretemathematics
permutationandcombination
recurrence
#recurrencerelations
0
votes
1
answer
36
Mathematical Logic Ques:Self doubt
“Not every satisfiable logic is valid” Representation of it will be $1)\sim \left ( \forall S(x)\rightarrow V(x) \right )$ or $2)\sim \left ( \forall S(x)\vee V(x) \right )$ Among $1)$ and $2)$, which one is correct? and why?
answered
Jun 4
in
Mathematical Logic
by
Satbir
Boss
(
13.2k
points)

72
views
discretemathematics
mathematicallogic
0
votes
2
answers
37
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

88
views
graphtheory
+1
vote
1
answer
38
#ACE_ACADEMY_DISCRETE_MATHS_BOOKLET.
Which of the following is not true? (a) Number of edgedisjoint Hamiltonian cycles in $K_7$ is $3$ (b) If $G$ is a simple graph with $6$ vertices and the degree of each vertex is at least $3$, then the Hamiltonian cycle exists in ... simple graph with $5$ vertices and $7$ edges, then the Hamiltonian cycle exists in $G$ Please help me understand all the options.
answered
Jun 4
in
Graph Theory
by
chandan2teja
(
117
points)

31
views
discretemathematics
graphtheory
0
votes
1
answer
39
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

49
views
simplegraph
+2
votes
2
answers
40
GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
answered
Jun 4
in
Graph Theory
by
rballiwal
Active
(
1.2k
points)

102
views
graphtheory
discretemathematics
To see more, click for all the
questions in this category
.
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
IIITH Preparation and interview experience (M.Tech CSE)
My Journey To iiiTH Mtech Cse 2019
IIIT H INTERVIEW EXPERIENCE 2019
IIITH Interview Experience
Thanks GO!!
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
876
Graph Theory
803
Probability
991
Linear Algebra
685
Calculus
489
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.1k
Non GATE
1.4k
Others
1.4k
Admissions
595
Exam Queries
577
Tier 1 Placement Questions
23
Job Queries
72
Projects
18
Follow @csegate
Recent questions and answers in Discrete Mathematics
Recent Blog Comments
Sir till when i cn get my GO 2020 hardcopy. I cnt...
Wonderful experience bro! Something different...
Congrats
Delivery is not beyond July 15 for first 200...
for address change, to whom we have to mail? As I...
49,548
questions
54,169
answers
187,464
comments
71,120
users