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
Previous GATE Questions in Discrete Mathematics
39
votes
5
answers
331
GATE CSE 2000 | Question: 2.5
A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true? $R$ is not an equivalence relation $R$ is an equivalence relation having $1$ equivalence class $R$ is an equivalence relation having $2$ equivalence classes $R$ is an equivalence relation having $3$ equivalence classes
A relation $R$ is defined on the set of integers as $xRy$ iff $(x + y)$ is even. Which of the following statements is true?$R$ is not an equivalence relation$R$ is an equ...
Kathleen
14.3k
views
Kathleen
asked
Sep 14, 2014
Set Theory & Algebra
gatecse-2000
set-theory&algebra
relations
normal
+
–
37
votes
4
answers
332
GATE CSE 2000 | Question: 2.4
A polynomial $p(x)$ satisfies the following: $p(1) = p(3) = p(5) = 1$ $p(2) = p(4) = -1$ The minimum degree of such a polynomial is $1$ $2$ $3$ $4$
A polynomial $p(x)$ satisfies the following:$p(1) = p(3) = p(5) = 1$ $p(2) = p(4) = -1$The minimum degree of such a polynomial is$1$$2$$3$$4$
Kathleen
8.0k
views
Kathleen
asked
Sep 14, 2014
Set Theory & Algebra
gatecse-2000
set-theory&algebra
normal
polynomials
+
–
39
votes
6
answers
333
GATE CSE 2000 | Question: 1.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$
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$
Kathleen
10.2k
views
Kathleen
asked
Sep 14, 2014
Combinatory
gatecse-2000
easy
pigeonhole-principle
combinatory
+
–
13
votes
1
answer
334
GATE CSE 1992 | Question: 15.a
Use Modus ponens $(A, A → B |= B)$ or resolution to show that the following set is inconsistent: $Q(x) \rightarrow P (x) \vee \sim R (a)$ $R (a) \vee \sim Q(a)$ $Q(a)$ $\sim P (y)$ where $x$ and $y$ are universally quantified variables, $a$ is a constant and $P, Q, R$ are monadic predicates.
Use Modus ponens $(A, A → B |= B)$ or resolution to show that the following set is inconsistent:$Q(x) \rightarrow P (x) \vee \sim R (a)$$R (a) \vee \sim Q(a)$$Q(a)$$\si...
Kathleen
3.5k
views
Kathleen
asked
Sep 13, 2014
Mathematical Logic
gate1992
normal
mathematical-logic
propositional-logic
descriptive
+
–
40
votes
4
answers
335
GATE CSE 1992 | Question: 14a
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
If $G$ is a group of even order, then show that there exists an element $a≠e$, the identity in $G$, such that $a^2 = e$.
Kathleen
7.3k
views
Kathleen
asked
Sep 13, 2014
Set Theory & Algebra
gate1992
set-theory&algebra
group-theory
normal
descriptive
proof
+
–
33
votes
3
answers
336
GATE CSE 1992 | Question: 03,iii
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
How many edges can there be in a forest with $p$ components having $n$ vertices in all?
Kathleen
6.5k
views
Kathleen
asked
Sep 13, 2014
Graph Theory
gate1992
graph-theory
graph-connectivity
descriptive
+
–
24
votes
4
answers
337
GATE CSE 1992 | Question: 02,xvi
Which of the following is/are a tautology? $a \vee b \to b \wedge c$ $a \wedge b \to b \vee c$ $a \vee b \to \left(b \to c \right)$ $a \to b \to \left(b \to c \right)$
Which of the following is/are a tautology?$a \vee b \to b \wedge c$$a \wedge b \to b \vee c$$a \vee b \to \left(b \to c \right)$$a \to b \to \left(b \to c \right)$
Kathleen
10.9k
views
Kathleen
asked
Sep 13, 2014
Mathematical Logic
gate1992
mathematical-logic
easy
propositional-logic
multiple-selects
+
–
9
votes
4
answers
338
GATE CSE 1992 | Question: 02,viii
A non-planar graph with minimum number of vertices has $9$ edges, $6$ vertices $6$ edges, $4$ vertices $10$ edges, $5$ vertices $9$ edges, $5$ vertices
A non-planar graph with minimum number of vertices has$9$ edges, $6$ vertices$6$ edges, $4$ vertices$10$ edges, $5$ vertices$9$ edges, $5$ vertices
Kathleen
3.3k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1992
graph-theory
normal
graph-planarity
+
–
10
votes
1
answer
339
GATE CSE 1992 | Question: 01,x
Maximum number of edges in a planar graph with $n$ vertices is _____
Maximum number of edges in a planar graph with $n$ vertices is _____
Kathleen
5.6k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1992
graph-theory
graph-planarity
easy
fill-in-the-blanks
+
–
52
votes
2
answers
340
GATE CSE 1991 | Question: 16,a
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's.$
Find the number of binary strings $w$ of length $2n$ with an equal number of $1's$ and $0's$ and the property that every prefix of $w$ has at least as many $0's$ as $1's....
Kathleen
6.6k
views
Kathleen
asked
Sep 12, 2014
Combinatory
gate1991
combinatory
normal
descriptive
catalan-number
+
–
41
votes
9
answers
341
GATE CSE 1991 | Question: 03,xii
If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim F_3$ are both tautologies, then which of the following is true: Both $F_1$ and $F_2$ are tautologies The conjunction $F_1 \land F_2$ is not satisfiable Neither is tautologous Neither is satisfiable None of the above
If $F_1$, $F_2$ and $F_3$ are propositional formulae such that $F_1 \land F_2 \rightarrow F_3$ and $F_1 \land F_2 \rightarrow \sim F_3$ are both tautologies, then which ...
Kathleen
9.3k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gate1991
mathematical-logic
normal
propositional-logic
multiple-selects
+
–
43
votes
4
answers
342
GATE CSE 1991 | Question: 02-iv
Match the pairs in the following questions by writing the corresponding letters only. ...
Match the pairs in the following questions by writing the corresponding letters only.$$\begin{array}{|c|l|c|l|} \hline A. & \text{The number of distinct binary tree} & P....
Kathleen
5.1k
views
Kathleen
asked
Sep 12, 2014
Combinatory
gate1991
combinatory
normal
match-the-following
+
–
51
votes
4
answers
343
GATE CSE 1991 | Question: 01,xv
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
Kathleen
11.8k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1991
graph-theory
graph-connectivity
normal
fill-in-the-blanks
+
–
19
votes
3
answers
344
GATE CSE 1991 | Question: 01,xiv
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
If the longest chain in a partial order is of length $n$, then the partial order can be written as a _____ of $n$ antichains.
Kathleen
5.9k
views
Kathleen
asked
Sep 12, 2014
Set Theory & Algebra
gate1991
set-theory&algebra
partial-order
normal
fill-in-the-blanks
+
–
114
votes
9
answers
345
GATE CSE 2012 | Question: 38
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$
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$$36...
gatecse
35.4k
views
gatecse
asked
Sep 12, 2014
Graph Theory
gatecse-2012
graph-theory
normal
marks-to-all
counting
+
–
31
votes
7
answers
346
GATE CSE 2008 | Question: 31
$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent? $P ∨ \neg Q$ $\neg(\neg P ∧ Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ \neg Q)$ $(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P ∧ Q)$ Only I and II Only I, II and III Only I, II and IV All of I, II, III and IV
$P$ and $Q$ are two propositions. Which of the following logical expressions are equivalent?$P ∨ \neg Q$$\neg(\neg P ∧ Q)$$(P ∧ Q) ∨ (P ∧ \neg Q) ∨ (\neg P �...
Kathleen
8.6k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gatecse-2008
normal
mathematical-logic
propositional-logic
+
–
71
votes
5
answers
347
GATE CSE 2008 | Question: 30
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown automaton. Let $\text{equivalent}$ ...
Let $\text{fsa}$ and $\text{pda}$ be two predicates such that $\text{fsa}(x)$ means $x$ is a finite state automaton and $\text{pda}(y)$ means that $y$ is a pushdown autom...
Kathleen
14.4k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gatecse-2008
easy
mathematical-logic
first-order-logic
+
–
17
votes
8
answers
348
GATE CSE 2008 | Question: 24
Let $P =\sum \limits_ {i\;\text{odd}}^{1\le i \le 2k} i$ and $Q = \sum\limits_{i\;\text{even}}^{1 \le i \le 2k} i$, where $k$ is a positive integer. Then $P = Q - k$ $P = Q + k$ $P = Q$ $P = Q + 2k$
Let $P =\sum \limits_ {i\;\text{odd}}^{1\le i \le 2k} i$ and $Q = \sum\limits_{i\;\text{even}}^{1 \le i \le 2k} i$, where $k$ is a positive integer. Then$P = Q - k$$P = Q...
Kathleen
6.1k
views
Kathleen
asked
Sep 11, 2014
Combinatory
gatecse-2008
combinatory
easy
summation
+
–
39
votes
7
answers
349
GATE CSE 2008 | Question: 23
Which of the following statements is true for every planar graph on $n$ vertices? The graph is connected The graph is Eulerian The graph has a vertex-cover of size at most $\frac{3n}{4}$ The graph has an independent set of size at least $\frac{n}{3}$
Which of the following statements is true for every planar graph on $n$ vertices?The graph is connectedThe graph is EulerianThe graph has a vertex-cover of size at most $...
Kathleen
65.3k
views
Kathleen
asked
Sep 11, 2014
Graph Theory
gatecse-2008
graph-theory
normal
graph-planarity
+
–
29
votes
8
answers
350
GATE CSE 2008 | Question: 2
If $P, Q, R$ are subsets of the universal set U, then $(P\cap Q\cap R) \cup (P^c \cap Q \cap R) \cup Q^c \cup R^c$ is $Q^c \cup R^c$ $P \cup Q^c \cup R^c$ $P^c \cup Q^c \cup R^c$ U
If $P, Q, R$ are subsets of the universal set U, then $$(P\cap Q\cap R) \cup (P^c \cap Q \cap R) \cup Q^c \cup R^c$$ is$Q^c \cup R^c$$P \cup Q^c \cup R^c$$P^c \cup Q^c \c...
Kathleen
9.5k
views
Kathleen
asked
Sep 11, 2014
Set Theory & Algebra
gatecse-2008
normal
set-theory&algebra
set-theory
+
–
Page:
« prev
1
...
12
13
14
15
16
17
18
19
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register