Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Recent
Hot!
Most votes
Most answers
Most views
Previous GATE
Featured
Hot questions in Discrete Mathematics
7
votes
3
answers
91
GATE CSE 2023 | Question: 45
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=\{1,2, \ldots\}$ denote the set of all possible colors. Color the vertices ... $\Delta(G)$. The number of colors used is equal to the chromatic number of $G$.
Let $G$ be a simple, finite, undirected graph with vertex set $\left\{v_{1}, \ldots, v_{n}\right\}$. Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N}=...
admin
8.4k
views
admin
asked
Feb 15, 2023
Graph Theory
gatecse-2023
graph-theory
graph-coloring
multiple-selects
2-marks
+
–
44
votes
9
answers
92
GATE CSE 2017 Set 2 | Question: 23
$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 _________ .
$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 _________ .
Madhav
17.6k
views
Madhav
asked
Feb 14, 2017
Graph Theory
gatecse-2017-set2
graph-theory
numerical-answers
degree-of-graph
+
–
48
votes
10
answers
93
GATE CSE 2017 Set 1 | Question: 29
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
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 \r...
Arjun
10.7k
views
Arjun
asked
Feb 14, 2017
Mathematical Logic
gatecse-2017-set1
mathematical-logic
propositional-logic
+
–
77
votes
9
answers
94
GATE CSE 2006 | Question: 25
Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $ \sum_{i=1}^{m} f(i)$ is: $3m$ $3n$ $2m+1$ $2n+1$
Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is...
Rucha Shelke
11.1k
views
Rucha Shelke
asked
Sep 18, 2014
Set Theory & Algebra
gatecse-2006
set-theory&algebra
normal
functions
+
–
39
votes
8
answers
95
GATE CSE 2002 | Question: 1.25, ISRO2008-30, ISRO2016-6
The maximum number of edges in a $n$-node undirected graph without self loops is $n^2$ $\frac{n(n-1)}{2}$ $n-1$ $\frac{(n+1)(n)}{2}$
The maximum number of edges in a $n$-node undirected graph without self loops is$n^2$$\frac{n(n-1)}{2}$$n-1$$\frac{(n+1)(n)}{2}$
Kathleen
18.7k
views
Kathleen
asked
Sep 15, 2014
Graph Theory
gatecse-2002
graph-theory
easy
isro2008
isro2016
graph-connectivity
+
–
42
votes
8
answers
96
GATE CSE 2004 | Question: 73
The inclusion of which of the following sets into $S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3, 4, 5\right\} \right\} $ is necessary and sufficient to make $S$ a complete lattice under the partial order defined by ... $\{1\}, \{1, 3\}$ $\{1\}, \{1, 3\}, \{1, 2, 3, 4\}, \{1, 2, 3, 5\}$
The inclusion of which of the following sets into$S = \left\{ \left\{1, 2\right\}, \left\{1, 2, 3\right\}, \left\{1, 3, 5\right\}, \left\{1, 2, 4\right\}, \left\{1, 2, 3,...
Kathleen
12.9k
views
Kathleen
asked
Sep 18, 2014
Set Theory & Algebra
gatecse-2004
set-theory&algebra
partial-order
normal
+
–
49
votes
11
answers
97
GATE CSE 2009 | Question: 2
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n > 2$. $2$ $3$ $n-1$ $n$
What is the chromatic number of an $n$ vertex simple connected graph which does not contain any odd length cycle? Assume $n 2$.$2$$3$$n-1$ $n$
gatecse
13.2k
views
gatecse
asked
Sep 15, 2014
Graph Theory
gatecse-2009
graph-theory
graph-coloring
normal
+
–
60
votes
6
answers
98
GATE CSE 2014 Set 1 | Question: 50
Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is _______.
Let ܵ$S$ denote the set of all functions $f:\{0,1\}^4 \to \{0,1\}$. Denote by $N$ the number of functions from S to the set $\{0,1\}$. The value of $ \log_2 \log_2N $ is...
go_editor
12.6k
views
go_editor
asked
Sep 28, 2014
Set Theory & Algebra
gatecse-2014-set1
set-theory&algebra
functions
combinatory
numerical-answers
+
–
58
votes
6
answers
99
GATE CSE 2003 | Question: 31
Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S \(\to\) {True, False} be a predicate defined on S. Suppose that P(a) = True, P(b) = False and P(x) \(\implies\) P(y) for all $x, y \in S$ satisfying $x \leq y$ ... for all x \(\in\) S such that b ≤ x and x ≠ c P(x) = False for all x \(\in\) S such that a ≤ x and b ≤ x
Let $(S, \leq)$ be a partial order with two minimal elements a and b, and a maximum element c. Let P: S \(\to\) {True, False} be a predicate defined on S. Suppose that P(...
Kathleen
11.8k
views
Kathleen
asked
Sep 16, 2014
Set Theory & Algebra
gatecse-2003
set-theory&algebra
partial-order
normal
propositional-logic
+
–
22
votes
5
answers
100
GATE CSE 1996 | Question: 1.2
Let $X = \{2, 3, 6, 12, 24\}$, Let $\leq$ be the partial order defined by $X \leq Y$ if $x$ divides $y$. Number of edges in the Hasse diagram of $(X, \leq)$ is $3$ $4$ $9$ None of the above
Let $X = \{2, 3, 6, 12, 24\}$, Let $\leq$ be the partial order defined by $X \leq Y$ if $x$ divides $y$. Number of edges in the Hasse diagram of $(X, \leq)$ is$3$$4$$9$No...
Kathleen
13.4k
views
Kathleen
asked
Oct 9, 2014
Set Theory & Algebra
gate1996
set-theory&algebra
partial-order
normal
+
–
38
votes
7
answers
101
GATE CSE 1999 | Question: 2.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
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 th...
Kathleen
12.3k
views
Kathleen
asked
Sep 23, 2014
Combinatory
gate1999
combinatory
normal
+
–
45
votes
10
answers
102
GATE IT 2005 | Question: 33
Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of $C?$ $n$ $n+1$ $2^{n-1} + 1$ $n!$
Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1 \subset S_2$ or $...
Ishrat Jahan
11.9k
views
Ishrat Jahan
asked
Nov 3, 2014
Set Theory & Algebra
gateit-2005
set-theory&algebra
normal
set-theory
+
–
14
votes
3
answers
103
GATE CSE 2023 | Question: 38
Let $U=\{1,2, \ldots, n\},$ where $n$ is a large positive integer greater than $1000.$ Let $k$ be a positive integer less than $n$. Let $A, B$ be subsets of $U$ with $|A|=|B|=k$ and $A \cap B=\emptyset$. We say that a permutation of $U$ separates $A$ from $B$ if ... $2\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k) !(k !)^{2}$
Let $U=\{1,2, \ldots, n\},$ where $n$ is a large positive integer greater than $1000.$ Let $k$ be a positive integer less than $n$. Let $A, B$ be subsets of $U$ with $|A|...
admin
6.6k
views
admin
asked
Feb 15, 2023
Combinatory
gatecse-2023
combinatory
counting
2-marks
+
–
7
votes
4
answers
104
GATE CSE 2024 | Set 2 | Question: 2
Let $p$ and $q$ be the following propositions: $p$ : Fail grade can be given. $q$ : Student scores more than $50 \%$ marks. Consider the statement: "Fail grade cannot be given when student scores more than $50 \%$ marks." ... above statement in propositional logic? $q \rightarrow \neg p$ $q \rightarrow p$ $p \rightarrow q$ $\neg p \rightarrow q$
Let $p$ and $q$ be the following propositions:$p$ : Fail grade can be given.$q$ : Student scores more than $50 \%$ marks.Consider the statement: "Fail grade c...
Arjun
3.4k
views
Arjun
asked
Feb 16
Mathematical Logic
gatecse2024-set2
mathematical-logic
+
–
0
votes
2
answers
105
Discrete Mathematics and Its Applications by Kenneth H. Rosen
From where can i get full solution of Discrete Mathematics and Its Applications by Kenneth H. Rosen ?
From where can i get full solution of Discrete Mathematics and Its Applications by Kenneth H. Rosen ?
kaleen bhaiya
18.8k
views
kaleen bhaiya
asked
Jan 23, 2022
Mathematical Logic
discrete-mathematics
kenneth-rosen
+
–
58
votes
6
answers
106
GATE CSE 2003 | Question: 72
The following resolution rule is used in logic programming. Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$ Which of the following statements related to this rule is FALSE? $((P ∨ R)∧(Q ∨ ¬R))⇒(P ∨ Q)$ ... if $(P ∨ R)∧(Q ∨ ¬R)$ is satisfiable $(P ∨ Q)⇒ \text{FALSE}$ if and only if both $P$ and $Q$ are unsatisfiable
The following resolution rule is used in logic programming.Derive clause $(P \vee Q)$ from clauses $(P\vee R),(Q \vee ¬R)$Which of the following statements related to th...
Kathleen
14.3k
views
Kathleen
asked
Sep 17, 2014
Mathematical Logic
gatecse-2003
mathematical-logic
normal
propositional-logic
+
–
50
votes
4
answers
107
GATE CSE 2005 | Question: 41
What is the first order predicate calculus statement equivalent to the following? "Every teacher is liked by some student" $∀(x)\left[\text{teacher}\left(x\right) → ∃(y) \left[\text{student}\left(y\right) → \text{likes}\left(y,x\right)\right]\right]$ ...
What is the first order predicate calculus statement equivalent to the following?"Every teacher is liked by some student"$∀(x)\left[\text{teacher}\left(x\right) → ∃...
gatecse
11.8k
views
gatecse
asked
Sep 21, 2014
Mathematical Logic
gatecse-2005
mathematical-logic
easy
first-order-logic
+
–
38
votes
3
answers
108
GATE CSE 2021 Set 1 | Question: 19
There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that: The fastest computer gets the toughest job and the slowest computer gets the easiest job. Every computer gets at least one job. The number of ways in which this can be done is ___________.
There are $6$ jobs with distinct difficulty levels, and $3$ computers with distinct processing speeds. Each job is assigned to a computer such that:The fastest computer g...
Arjun
11.9k
views
Arjun
asked
Feb 18, 2021
Combinatory
gatecse-2021-set1
combinatory
counting
numerical-answers
1-mark
+
–
18
votes
3
answers
109
GATE CSE 2022 | Question: 22
The number of arrangements of six identical balls in three identical bins is _____________ .
The number of arrangements of six identical balls in three identical bins is _____________ .
Arjun
10.5k
views
Arjun
asked
Feb 15, 2022
Combinatory
gatecse-2022
numerical-answers
combinatory
balls-in-bins
1-mark
+
–
46
votes
3
answers
110
GATE CSE 2013 | Question: 47
Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ? $∀ x(∃ z(¬β )→∀ y(α))$ $∀x(∀ z(β )→∃ y(¬α))$ $∀x(∀ y(α)→∃z(¬β ))$ $∀x(∃ y(¬α)→∃z(¬β ))$
Which one of the following is NOT logically equivalent to $¬∃x(∀ y (α)∧∀z(β ))$ ?$∀ x(∃ z(¬β )→∀ y(α))$$∀x(∀ z(β )→∃ y(¬α))$$∀x(∀ y(�...
gatecse
12.0k
views
gatecse
asked
Aug 21, 2014
Mathematical Logic
mathematical-logic
normal
marks-to-all
gatecse-2013
first-order-logic
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
...
357
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register