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
Most viewed questions in Discrete Mathematics
87
votes
7
answers
1
GATE CSE 2004 | Question: 23, ISRO2007-32
Identify the correct translation into logical notation of the following assertion. Some boys in the class are taller than all the girls Note: $\text{taller} (x, y)$ is true if $x$ is taller than $y$ ... $(\exists x) (\text{boy}(x) \land (\forall y) (\text{girl}(y) \rightarrow \text{taller}(x, y)))$
Identify the correct translation into logical notation of the following assertion.Some boys in the class are taller than all the girlsNote: $\text{taller} (x, y)$ is true...
Kathleen
131k
views
Kathleen
asked
Sep 18, 2014
Mathematical Logic
gatecse-2004
mathematical-logic
easy
isro2007
first-order-logic
+
–
71
votes
5
answers
2
GATE CSE 2010 | Question: 30
Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$. Which one of the statements below expresses best the meaning of the formula, $\qquad∀x∃y∃t(¬F(x,y,t))$ Everyone can ... time No one can fool everyone all the time Everyone cannot fool some person all the time No one can fool some person at some time
Suppose the predicate $F(x, y, t)$ is used to represent the statement that person $x$ can fool person $y$ at time $t$.Which one of the statements below expresses best the...
gatecse
82.3k
views
gatecse
asked
Sep 21, 2014
Mathematical Logic
gatecse-2010
mathematical-logic
easy
first-order-logic
+
–
39
votes
7
answers
3
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
+
–
58
votes
7
answers
4
GATE IT 2008 | Question: 4
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes? $5$ $4$ $3$ $2$
What is the size of the smallest $\textsf{MIS}$ (Maximal Independent Set) of a chain of nine nodes?$5$$4$$3$$2$
Ishrat Jahan
59.0k
views
Ishrat Jahan
asked
Oct 27, 2014
Graph Theory
gateit-2008
normal
graph-connectivity
+
–
60
votes
10
answers
5
GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
Kathleen
50.4k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-matching
normal
+
–
5
votes
2
answers
6
How many transitive relations are there on a set with n elements if a)n=1 b) n=2 c) n=3
How many transitive relations are there on a set with n elements if a)n=1 b) n=2 c) n=3
How many transitive relations are there on a set with n elements ifa)n=1 b) n=2 c) n=3
Sanjay Sharma
47.3k
views
Sanjay Sharma
asked
Mar 7, 2017
13
votes
3
answers
7
relation
Number of relations $S$ over set $\{0,1,2,3 \}$ such that $(x,y) \in S \Rightarrow x = y$
Number of relations $S$ over set $\{0,1,2,3 \}$ such that $(x,y) \in S \Rightarrow x = y$
Lakshman Bhaiya
44.5k
views
Lakshman Bhaiya
asked
Dec 27, 2017
Set Theory & Algebra
set-theory&algebra
relations
+
–
113
votes
9
answers
8
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
34.9k
views
gatecse
asked
Sep 12, 2014
Graph Theory
gatecse-2012
graph-theory
normal
marks-to-all
counting
+
–
77
votes
12
answers
9
GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
Kathleen
34.8k
views
Kathleen
asked
Oct 4, 2014
Graph Theory
gate1994
graph-theory
graph-connectivity
combinatory
normal
isro2008
counting
+
–
1
votes
1
answer
10
Graph
1. Suppose that G is a non-directed graph with 12 edges. Suppose that G has 6 vertices of degree 3 and the rest have degrees less than 3. The minimum number of vertices G can have? a) 2 b) 0 c)1 d)3 I am getting 3..plz verify
1. Suppose that G is a non-directed graph with 12 edges. Suppose that G has 6 vertices of degree 3 and the rest have degrees less than 3. The minimum number of vertices G...
cse23
33.2k
views
cse23
asked
Jan 20, 2017
67
votes
10
answers
11
GATE CSE 2016 Set 1 | Question: 27
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
Consider the recurrence relation $a_1 =8 , a_n =6n^2 +2n+a_{n-1}$. Let $a_{99}=K\times 10^4$. The value of $K$ is __________.
Sandeep Singh
29.3k
views
Sandeep Singh
asked
Feb 12, 2016
Combinatory
gatecse-2016-set1
combinatory
recurrence-relation
normal
numerical-answers
+
–
39
votes
9
answers
12
GATE CSE 2014 Set 2 | Question: 3
The maximum number of edges in a bipartite graph on $12$ vertices is____
The maximum number of edges in a bipartite graph on $12$ vertices is____
go_editor
27.1k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set2
graph-theory
graph-connectivity
numerical-answers
normal
+
–
101
votes
10
answers
13
GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $...
go_editor
26.8k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
+
–
19
votes
2
answers
14
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric? Please explain how to calculate .
On a set of n elements, how many relations are there that are both irreflexive and antisymmetric?Please explain how to calculate .
shree
26.4k
views
shree
asked
Oct 24, 2014
Set Theory & Algebra
set-theory&algebra
relations
+
–
57
votes
17
answers
15
GATE CSE 2016 Set 1 | Question: 26
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
The coefficient of $x^{12}$ in $\left(x^{3}+x^{4}+x^{5}+x^{6}+\dots \right)^{3}$ is ___________.
Sandeep Singh
25.8k
views
Sandeep Singh
asked
Feb 12, 2016
Combinatory
gatecse-2016-set1
combinatory
generating-functions
normal
numerical-answers
+
–
76
votes
5
answers
16
GATE CSE 2007 | Question: 23
Which of the following graphs has an Eulerian circuit? Any $k$-regular graph where $k$ is an even number. A complete graph on $90$ vertices. The complement of a cycle on $25$ vertices. None of the above
Which of the following graphs has an Eulerian circuit?Any $k$-regular graph where $k$ is an even number.A complete graph on $90$ vertices.The complement of a cycle on $25...
Kathleen
25.3k
views
Kathleen
asked
Sep 21, 2014
Graph Theory
gatecse-2007
graph-theory
normal
graph-connectivity
+
–
36
votes
6
answers
17
GATE CSE 2005 | Question: 7
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be: $O(n)$ $O(n \log n)$ $O \left( n^{\frac{3}{2}} \right)$ $O\left(n^3\right)$
The time complexity of computing the transitive closure of a binary relation on a set of $n$ elements is known to be:$O(n)$$O(n \log n)$$O \left( n^{\frac{3}{2}} \right)...
Kathleen
24.7k
views
Kathleen
asked
Sep 22, 2014
Set Theory & Algebra
gatecse-2005
set-theory&algebra
normal
relations
+
–
33
votes
9
answers
18
GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
makhdoom ghaya
24.6k
views
makhdoom ghaya
asked
Feb 13, 2015
Graph Theory
gatecse-2015-set1
graph-theory
graph-connectivity
normal
graph-planarity
numerical-answers
+
–
76
votes
6
answers
19
GATE CSE 2008 | Question: 42
$G$ is a graph on $n$ vertices and $2n-2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$? For every subset of $k$ vertices, the induced subgraph has at ... least $2$ edge-disjoint paths between every pair of vertices. There are at least $2$ vertex-disjoint paths between every pair of vertices.
$G$ is a graph on $n$ vertices and $2n-2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$?For...
Akshay Jindal
23.6k
views
Akshay Jindal
asked
Sep 27, 2014
Graph Theory
gatecse-2008
graph-connectivity
normal
+
–
33
votes
6
answers
20
GATE CSE 1996 | Question: 1.4
Which of the following statements is FALSE? The set of rational numbers is an abelian group under addition The set of integers in an abelian group under addition The set of rational numbers form an abelian group under multiplication The set of real numbers excluding zero is an abelian group under multiplication
Which of the following statements is FALSE?The set of rational numbers is an abelian group under additionThe set of integers in an abelian group under additionThe set of ...
Kathleen
23.0k
views
Kathleen
asked
Oct 9, 2014
Set Theory & Algebra
gate1996
set-theory&algebra
group-theory
normal
+
–
Page:
1
2
3
4
5
6
...
356
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register