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
GATE20001.1
The minimum number of cards to be dealt from an arbitrarily shuffled deck of $52$ cards to guarantee that three cards are from same suit is $3$ $8$ $9$ $12$
answered
21 hours
ago
in
Combinatory
by
Asim Siddiqui 4
Active
(
1.2k
points)

2.9k
views
gate2000
easy
pigeonholeprinciple
permutationandcombination
+25
votes
4
answers
2
GATE200673
The $2^n$ vertices of a graph $G$ corresponds to all subsets of a set of size $n$, for $n \geq 6$. Two vertices of $G$ are adjacent if and only if the corresponding sets intersect in exactly two elements. The number of connected components in $G$ is: $n$ $n + 2$ $2^{\frac{n}{2}}$ $\frac{2^{n}}{n}$
answered
1 day
ago
in
Graph Theory
by
shaktisingh
(
241
points)

2.4k
views
gate2006
graphtheory
normal
graphconnectivity
+38
votes
6
answers
3
GATE200544
What is the minimum number of ordered pairs of nonnegative numbers that should be chosen to ensure that there are two pairs $(a,b)$ and $(c,d)$ in the chosen set such that, $a \equiv c\mod 3$ and $b \equiv d \mod 5$ $4$ $6$ $16$ $24$
answered
3 days
ago
in
Combinatory
by
techbd123
Active
(
1.4k
points)

4.2k
views
gate2005
settheory&algebra
normal
pigeonholeprinciple
+3
votes
2
answers
4
CMI2015A10
The school athletics coach has to choose 4 students for the relay team. He calculates that there are 3876 ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the ... taken into account? Between 12,000 and 25,000 Between 75,000 and 99,999 Between 30,000 and 60,000 More than 100,000
answered
3 days
ago
in
Combinatory
by
chirudeepnamini
Active
(
1.8k
points)

92
views
cmi2015
permutationandcombination
+21
votes
5
answers
5
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
answered
4 days
ago
in
Set Theory & Algebra
by
JashanArora
Junior
(
827
points)

4.6k
views
gate2018
settheory&algebra
countableuncountableset
normal
+1
vote
2
answers
6
set theory
answered
4 days
ago
in
Set Theory & Algebra
by
Spidey_guy
(
111
points)

50
views
settheory&algebra
discretemathematics
engineeringmathematics
sets
+50
votes
7
answers
7
GATE2016228
Consider a set $U$ of $23$ different compounds in a chemistry lab. There is a subset $S$ of $U$ of $9$ compounds, each of which reacts with exactly $3$ compounds of $U$. Consider the following statements: Each compound in U \ S reacts with an odd number ... in U \ S reacts with an even number of compounds. Which one of the above statements is ALWAYS TRUE? Only I Only II Only III None.
answered
4 days
ago
in
Set Theory & Algebra
by
Spidey_guy
(
111
points)

4.8k
views
gate20162
settheory&algebra
difficult
sets
+32
votes
8
answers
8
GATE19941.6, ISRO200829
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
answered
4 days
ago
in
Graph Theory
by
Saurabh666
(
389
points)

9.3k
views
gate1994
graphtheory
permutationandcombination
normal
isro2008
counting
0
votes
1
answer
9
Rosen 7e Recurrence Relation Exercise8.1 Question no25 page no511
How many bit sequences of length seven contain an even number of 0s? I'm trying to solve this using recurrence relation Is my approach correct? Let T(n) be the string having even number of 0s T(1)=1 {1} T(2)=2 {00, 11} T(3)=4 {001, ... add 0 to strings of length n1 having odd number of 0s T(n)=T(n1) Hence, we have T(n)=2T(n1)
answered
6 days
ago
in
Combinatory
by
anonymousgamer
(
11
points)

53
views
kennethrosen
discretemathematics
permutationandcombination
#recurrencerelations
recurrence
+2
votes
3
answers
10
Made easy
What is the chromatic number of following graphs? 1) 2)
answered
Oct 16
in
Graph Theory
by
chirudeepnamini
Active
(
1.8k
points)

167
views
graphcoloring
discrete
engineeringmathematics
0
votes
1
answer
11
Combinatorics
There are 6n flowers of one type and 3 flowers of second type, total no. Of garlands possible?
answered
Oct 11
in
Combinatory
by
shivamgo
(
11
points)

29
views
permutationandcombination
+8
votes
4
answers
12
GATE19893v
Answer the following: Which of the following wellformed formulas are equivalent? $P \rightarrow Q$ $\neg Q \rightarrow \neg P$ $\neg P \vee Q$ $\neg Q \rightarrow P$
answered
Oct 8
in
Mathematical Logic
by
vupadhayayx86
Active
(
1.4k
points)

587
views
gate1989
normal
mathematicallogic
propositionallogic
+3
votes
2
answers
13
TIFR2010MathsA1
A cyclic group of order 60 has 12 Generators 15 Generators 16 Generators 20 Generators
answered
Oct 6
in
Set Theory & Algebra
by
Lakshman Patel RJIT
Veteran
(
51.5k
points)

940
views
tifrmaths2010
groups
+2
votes
3
answers
14
TIFR2014MathsB4
Let $H_{1}$, $H_{2}$ be two distinct subgroups of a finite group $G$, each of order $2$. Let $H$ be the smallest subgroup containing $H_{1}$ and $H_{2}$. Then the order of $H$ is Always 2 Always 4 Always 8 None of the above.
answered
Oct 5
in
Set Theory & Algebra
by
Harry Richie
(
17
points)

328
views
tifrmaths2014
settheory&algebra
groups
+1
vote
1
answer
15
TIFR2014MathsA15
How many proper subgroups does the group $\mathbb{Z} ⊕ \mathbb{Z}$ have? $1$ $2$ $3$ Infinitely many
answered
Oct 5
in
Set Theory & Algebra
by
Harry Richie
(
17
points)

182
views
tifrmaths2014
groups
+13
votes
2
answers
16
GATE201529
The number of divisors of $2100$ is ____.
answered
Oct 3
in
Set Theory & Algebra
by
JashanArora
Junior
(
827
points)

3.2k
views
gate20152
settheory&algebra
numbertheory
easy
numericalanswers
+5
votes
10
answers
17
GATE201921
The value of $3^{51} \text{ mod } 5$ is _____
answered
Oct 3
in
Combinatory
by
techbd123
Active
(
1.4k
points)

3k
views
gate2019
numericalanswers
permutationandcombination
modulararithmetic
+1
vote
1
answer
18
graph Theory
Consider an undirected graph G where selfloops are not allowed. The vertex set of G is {(i,j):1<=i<=12,1<=j<=12}. There is an edge between (a, b) and (c, d) if ac<=1 and bd<=1. The number of edges in this graph is __________.
answered
Oct 1
in
Graph Theory
by
Mac2
(
11
points)

116
views
discretemathematics
graphtheory
+5
votes
2
answers
19
GATE199525b
Determine the number of positive integers $(\leq 720)$ which are not divisible by any of $2,3$ or $5.$
answered
Sep 27
in
Set Theory & Algebra
by
techbd123
Active
(
1.4k
points)

237
views
gate1995
settheory&algebra
numericalanswers
sets
+31
votes
3
answers
20
GATE20012.15
How many undirected graphs (not necessarily connected) can be constructed out of a given set $V=\{v_1, v_2, \dots v_n\}$ of $n$ vertices? $\frac{n(n1)} {2}$ $2^n$ $n!$ $2^\frac{n(n1)} {2} $
answered
Sep 26
in
Graph Theory
by
HeartBleed
Junior
(
691
points)

3.9k
views
gate2001
graphtheory
normal
counting
0
votes
1
answer
21
Kenneth Rosen Edition 7th Exercise 2.2 Question 14 (Page No. 136)
Find the sets $A$ and $B$ if $AB=\left \{ 1,5,7,8 \right \}, BA=\left \{ 2,10 \right \},$ and $A \cap B=\left \{ 3,6,9 \right \}.$
answered
Sep 24
in
Set Theory & Algebra
by
anurag_cs
(
41
points)

15
views
kennethrosen
discretemathematics
settheory&algebra
0
votes
2
answers
22
SelfDoubt:Mathematical logic
“Every asymmetric relation is antisymmetric” Is this statement is True or False? I think it is false, because asymmetric relation never allows loops and antisymmetric relation allows loops. Am I not correct?
answered
Sep 24
in
Set Theory & Algebra
by
anurag_cs
(
41
points)

31
views
discretemathematics
+33
votes
9
answers
23
GATE2014351
If $G$ is the forest with $n$ vertices and $k$ connected components, how many edges does $G$ have? $\left\lfloor\frac {n}{k}\right\rfloor$ $\left\lceil \frac{n}{k} \right\rceil$ $nk$ $nk+1$
answered
Sep 24
in
Graph Theory
by
HeartBleed
Junior
(
691
points)

4.4k
views
gate20143
graphtheory
graphconnectivity
normal
+17
votes
6
answers
24
GATE199810a
Prove by induction that the expression for the number of diagonals in a polygon of $n$ sides is $\frac{n(n3)}{2}$
answered
Sep 20
in
Set Theory & Algebra
by
Gaurav Yadav
(
233
points)

1.2k
views
gate1998
settheory&algebra
descriptive
relations
+10
votes
3
answers
25
GATE199714
Let $R$ be a reflexive and transitive relation on a set $A$. Define a new relation $E$ on $A$ as $E=\{(a, b) \mid (a, b) \in R \text{ and } (b, a) \in R \}$ Prove that $E$ is an equivalence relation on $A$. Define a relation $\leq$ on the equivalence classes of $E$ ... $\exists a, b$ such that $a \in E_1, b \in E_2 \text{ and } (a, b) \in R$. Prove that $\leq$ is a partial order.
answered
Sep 19
in
Set Theory & Algebra
by
Sambhrant Maurya
Active
(
3.2k
points)

806
views
gate1997
settheory&algebra
relations
normal
proof
descriptive
+15
votes
4
answers
26
GATE19943.8
Give a relational algebra expression using only the minimum number of operators from $(∪, −)$ which is equivalent to $R$ $∩$ $S.$
answered
Sep 18
in
Set Theory & Algebra
by
Anurag007
(
11
points)

830
views
gate1994
settheory&algebra
normal
sets
descriptive
+3
votes
2
answers
27
UGCNETJune2019II5
For which values of $m$ and $n$ does the complete bipartite graph $k_{m,n}$ have a Hamiltonian circuit ? $m\neq n,\ \ m,n \geq 2$ $m\neq n,\ \ m,n \geq 3$ $m=n,\ \ m,n \geq 2$ $m= n,\ \ m,n \geq 3$
answered
Sep 17
in
Graph Theory
by
Raghava45
(
339
points)

169
views
ugcnetjune2019ii
graphtheory
+23
votes
5
answers
28
GATE200923
Which one of the following is the most appropriate logical formula to represent the statement? "Gold and silver ornaments are precious". The following notations are used: $G(x): x$ is a gold ornament $S(x): x$ is a silver ornament $P(x): x$ ... $\exists x((G(x) \wedge S(x)) \implies P(x))$ $\forall x((G(x) \vee S(x)) \implies P(x))$
answered
Sep 17
in
Mathematical Logic
by
manikantsharma
(
375
points)

1.7k
views
gate2009
mathematicallogic
easy
firstorderlogic
+13
votes
3
answers
29
ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?
answered
Sep 14
in
Graph Theory
by
rohith1001
Junior
(
549
points)

936
views
isi2016
graphtheory
trees
descriptive
0
votes
3
answers
30
Permutations and combinations
In how any ways can 8 different shirts be distributed among 4 different people so that each recieves 2 shirts?
answered
Sep 13
in
Combinatory
by
gajendercse
(
11
points)

252
views
permutationandcombination
+20
votes
4
answers
31
GATE19968
Let $F$ be the collection of all functions $f: \{1, 2, 3\} \to \{1, 2, 3\}$. If $f$ and $g \in F$, define an equivalence relation $\sim$ by $f\sim g$ if and only if $f(3) = g(3)$. Find the number of equivalence classes defined by $\sim$. Find the number of elements in each equivalence class.
answered
Sep 10
in
Set Theory & Algebra
by
Debargha Bhattacharj
Junior
(
653
points)

1.6k
views
gate1996
settheory&algebra
relations
functions
normal
descriptive
+1
vote
1
answer
32
REGARDING DISCRETE MATHS SYLLABUS
FIELD AND RING ARE IN SYLLABUS???
answered
Sep 10
in
Set Theory & Algebra
by
Arjun
Veteran
(
421k
points)

97
views
0
votes
2
answers
33
UGCNETDec2012III34
The power set of AUB, where A={2, 3, 5, 7} and B={2, 5, 8, 9}is 256 64 16 4
answered
Sep 9
in
Discrete Mathematics
by
omsanchitjain
(
33
points)

900
views
ugcnetdec2012iii
engineeringmathematics
discretemathematics
sets
+2
votes
2
answers
34
UGCNETDec2012II4
The power set of the set $\{ \Phi \}$ is $\{ \Phi \}$ $\{ \Phi, \{ \Phi \} \}$ $\{ 0 \}$ $\{ 0, \Phi , \{ \Phi \} \}$
answered
Sep 9
in
Set Theory & Algebra
by
omsanchitjain
(
33
points)

485
views
ugcnetdec2012ii
settheory&algebra
sets
powerset
+2
votes
3
answers
35
UGCNETDec2015II3
Which of the following is/are not true ? The set of negative integers is countable. The set of integers that are multiples of 7 is countable. The set of even integers is countable. The set of real numbers between 0 and 1⁄2 is countable. a and c b and d b only d only
answered
Sep 9
in
Set Theory & Algebra
by
omsanchitjain
(
33
points)

726
views
ugcnetdec2015ii
discretemathematics
settheory
0
votes
1
answer
36
Kenneth Rosen Edition 7th Exercise 1.6 Question 30 (Page No. 80)
Use resolution to show the hypotheses “Allen is a bad boy or Hillary is a good girl” and “Allen is a good boy or David is happy” imply the conclusion “Hillary is a good girl or David is happy.”
answered
Sep 7
in
Mathematical Logic
by
tejamach
(
11
points)

13
views
kennethrosen
discretemathematics
mathematicallogic
propositionallogic
+2
votes
1
answer
37
Countable and Uncountable Self Doubt 2
Which of the following is always correct? A. Cross product of two countable set is countable B. Cross product of two countable set is uncountable C. Cross product of two uncountable set is countable D. Cross product of uncountable ... E. Cross product of uncountable and countable set is countable F. Cross product of uncountable and countable set is uncountable
answered
Sep 5
in
Set Theory & Algebra
by
Sandee
(
11
points)

95
views
theoryofcomputation
countableuncountableset
settheory&algebra
+5
votes
3
answers
38
UGCNETJune2019II1
Consider the poset $( \{3,5,9,15,24,45 \}, \mid).$ Which of the following is correct for the given poset ? There exist a greatest element and a least element There exist a greatest element but not a least element There exist a least element but not a greatest element There does not exist a greatest element and a least element
answered
Sep 4
in
Set Theory & Algebra
by
bhupendrakumar
(
45
points)

460
views
ugcnetjune2019ii
poset
settheory&algebra
+1
vote
1
answer
39
How do I prepare Engineering Mathematics for Gate CS?
Good Morning, I want to start Engineering Mathematics and need help from you to know where to start and what would be the best sequence to complete the whole subject?
answered
Sep 4
in
Mathematical Logic
by
Akashniranjan
(
11
points)

479
views
preparation
general
+5
votes
2
answers
40
MadeEasy Test Series 2018: Graph Theory  Graph Coloring
answer given is 4. Please provide a detailed solution.
answered
Sep 3
in
Graph Theory
by
Rishav_Bhatt
(
141
points)

158
views
graphtheory
graphcoloring
madeeasytestseries
madeeasytestseries2018
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
Standard Book Exercise Questions for Computer Science
Resource to Learn Graph Theory Interactively
Recruitment to the post of Scientist/Engineer 'SC' (Electronics, Mechanical and Computer Science)
Standard Videos for Calculus
Standard Videos for Linear Algebra
All categories
General Aptitude
1.8k
Engineering Mathematics
7.3k
Discrete Mathematics
5.1k
Mathematical Logic
2.1k
Set Theory & Algebra
1.3k
Combinatory
879
Graph Theory
805
Probability
987
Linear Algebra
682
Calculus
493
Digital Logic
2.9k
Programming and DS
4.9k
Algorithms
4.4k
Theory of Computation
6.2k
Compiler Design
2.1k
Operating System
4.2k
Databases
4.1k
CO and Architecture
3.4k
Computer Networks
4.1k
Non GATE
1.6k
Others
1.8k
Admissions
595
Exam Queries
576
Tier 1 Placement Questions
23
Job Queries
72
Projects
17
Follow @csegate
Recent questions and answers in Discrete Mathematics
Recent Blog Comments
Are the answers also present ?
@Arjun sir , Is there any page or something where...
@arjun sir but u called about providing the pdfs...
But anyhow I appreciate this. The questions of...
All these PYQ blogs and standard videos blogs...
50,407
questions
55,862
answers
192,660
comments
91,653
users