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
40
votes
4
answers
331
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.2k
views
Kathleen
asked
Sep 13, 2014
Set Theory & Algebra
gate1992
set-theory&algebra
group-theory
normal
descriptive
proof
+
–
33
votes
3
answers
332
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.4k
views
Kathleen
asked
Sep 13, 2014
Graph Theory
gate1992
graph-theory
graph-connectivity
descriptive
+
–
24
votes
4
answers
333
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
334
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.2k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1992
graph-theory
normal
graph-planarity
+
–
10
votes
1
answer
335
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.5k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1992
graph-theory
graph-planarity
easy
fill-in-the-blanks
+
–
52
votes
2
answers
336
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.5k
views
Kathleen
asked
Sep 12, 2014
Combinatory
gate1991
combinatory
normal
descriptive
catalan-number
+
–
40
votes
9
answers
337
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.0k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gate1991
mathematical-logic
normal
propositional-logic
multiple-selects
+
–
43
votes
4
answers
338
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.0k
views
Kathleen
asked
Sep 12, 2014
Combinatory
gate1991
combinatory
normal
match-the-following
+
–
51
votes
4
answers
339
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.6k
views
Kathleen
asked
Sep 12, 2014
Graph Theory
gate1991
graph-theory
graph-connectivity
normal
fill-in-the-blanks
+
–
19
votes
3
answers
340
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.8k
views
Kathleen
asked
Sep 12, 2014
Set Theory & Algebra
gate1991
set-theory&algebra
partial-order
normal
fill-in-the-blanks
+
–
113
votes
9
answers
341
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.0k
views
gatecse
asked
Sep 12, 2014
Graph Theory
gatecse-2012
graph-theory
normal
marks-to-all
counting
+
–
31
votes
7
answers
342
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.4k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gatecse-2008
normal
mathematical-logic
propositional-logic
+
–
71
votes
5
answers
343
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.2k
views
Kathleen
asked
Sep 12, 2014
Mathematical Logic
gatecse-2008
easy
mathematical-logic
first-order-logic
+
–
17
votes
8
answers
344
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.0k
views
Kathleen
asked
Sep 11, 2014
Combinatory
gatecse-2008
combinatory
easy
summation
+
–
39
votes
7
answers
345
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.1k
views
Kathleen
asked
Sep 11, 2014
Graph Theory
gatecse-2008
graph-theory
normal
graph-planarity
+
–
29
votes
8
answers
346
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.4k
views
Kathleen
asked
Sep 11, 2014
Set Theory & Algebra
gatecse-2008
normal
set-theory&algebra
set-theory
+
–
78
votes
6
answers
347
GATE CSE 1992 | Question: 92,xv
Which of the following predicate calculus statements is/are valid? $(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$ $(\exists (x)) P(x) \wedge (\exists (x))Q(x) \implies (\exists (x)) (P(x) \wedge Q(x))$ ... $(\exists (x)) (P(x) \vee Q(x)) \implies \sim (\forall (x)) P(x) \vee (\exists (x)) Q(x)$
Which of the following predicate calculus statements is/are valid?$(\forall (x)) P(x) \vee (\forall(x))Q(x) \implies (\forall (x)) (P(x) \vee Q(x))$$(\exists (x)) P(x) \w...
Arjun
16.6k
views
Arjun
asked
Sep 2, 2014
Mathematical Logic
gate1992
mathematical-logic
normal
first-order-logic
+
–
46
votes
3
answers
348
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
+
–
33
votes
3
answers
349
GATE CSE 2013 | Question: 1
A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is TRUE about $\oplus$? Commutative but not associative Both commutative and associative Associative but not commutative Neither commutative nor associative
A binary operation $\oplus$ on a set of integers is defined as $x \oplus y = x^{2}+y^{2}$. Which one of the following statements is TRUE about $\oplus$?Commutative but no...
gatecse
7.6k
views
gatecse
asked
Aug 7, 2014
Set Theory & Algebra
gatecse-2013
set-theory&algebra
easy
binary-operation
+
–
26
votes
3
answers
350
GATE CSE 2012 | Question: 17
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the plane is equal to $3$ $4$ $5$ $6$
Let $G$ be a simple undirected planar graph on $10$ vertices with $15$ edges. If $G$ is a connected graph, then the number of bounded faces in any embedding of $G$ on the...
gatecse
10.1k
views
gatecse
asked
Aug 5, 2014
Graph Theory
gatecse-2012
graph-theory
graph-planarity
normal
+
–
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