Set Theory

• Set are the fundamental discrete structures on which all the discrete structures are
built. Sets are used to group objects together, formally speaking
• “A well-defined, unordered collection of distinct objects (Called elements or members
of a set) of same type”. Here the type is defined by the one who is defining the set.
For e.g. A = {0,2,4,6, ---}, B = {1,3,5, ---}, C= {x| x ∈ Natural number}
• A set is generally denoted usually by capital letter. The objects of a set called the
elements, or members of the set. A set is said to contain its elements. Lower case
letters are generally used to denote the element of the set.
• x ϵ A, means element x is a member of A
• x ∉ A means x is not a member of A
• Cardinality of a set— It is the number of elements present in a Set, denoted like |A|,
For e.g. A = {0,2,4,6}, |A| = 4.
• Representation of set
o Tabular/Roster representation of set- here a set is defined by actually listing
its members. Generally Used when set contains few elements. Used in complex
analysis or large sets. E.g.
▪ A = {a, e, i, o, u}
▪ B = {1, 2, 3, 4}
▪ C = {---- -4, -2, 0, 2, 4, -----}.
o Set Builder representations of set- here we specify the property which the
elements of the set must satisfy. E.g.
▪ A = {x| x is an odd positive number less than 10}
▪ A = {x | x ϵ English alphabet && x is vowel}
▪ B = {x | x ϵ N && x <5}
▪ C = {x | x ϵ Z && x%2 = 0}
 Standard notations

• Set of all Complex number(C) - A complex number is a number that can be expressed
in the form ‘a + bi’, where ‘a’ and ‘b’ are real numbers and ‘i’ is the imaginary unit,
that satisfies the equation i2 = −1. In this expression, ‘a’ is the real part and ‘b’ is the
imaginary part of the complex number.
• Set of all Real number(R) - A real number is a value that represents a quantity along
a continuous line, containing all of the rational numbers and all of the irrational
numbers.
• Set of all Rational number (Q) - A rational number is any number that can be
expressed as a fraction p/q of two integers, a numerator p and a non-zero
denominator q.
• Set of all Irrational number (R-Q or R/Q or P)- An irrational number is a real
number that cannot be expressed as a fraction i.e. as a ratio of integers.
Therefore, irrational numbers, when written as decimal numbers, do not terminate,
nor do they repeat. E.g. root2.
• Set of all Integer(Z) - An integer is a number that can be written without a fractional
component.
• Set of all Whole number(W) - A natural number. whole number in Science
Expand. whole number. A member of the set of positive integers and zero.
• Set of all-Natural number(N) - A natural number is a number that occurs commonly
and obviously in nature. The set of natural numbers, can be defined as N = {1,2,3, 4....
∞}
 • Finite set - If there are exactly ‘n’ distinct elements in S where ‘n’ is a nonnegative
integer, we say that S is a finite set. For e.g. A = {1,2,3,4} and ‘n’ is the cardinality of S.
• Infinite set – A set contain infinite number of elements is called infinite set, if the
counting of different elements of the set does not come to an end. For e.g. a set of
natural numbers.
• Countable set – A set is said to be countable if there can be a one to one mapping
between the elements of the set and natural numbers. E.g. Set of stars.
• Uncountable set – A set is said to be uncountable if there cannot be a one to one
mapping between the elements of the set and natural numbers. E.g. Set of real
numbers.

Q Which of the following is/are not true? (NET-Dec-2015)

(a)The set of negative integers is countable.
(b)The set of integers that are multiples of 7 is countable.
(c)The set of even integers is countable.
(d)The set of real numbers between 0 and ½ is countable.
(A) (a) and (c) (B) (b) and (d) (C) (b) only (D) (d) only
Answer: (D)
We must understand if a set is finite it must be countable for e.g. number of states in India.
but in set theory it is also possible that even if a set is infinite still it can be countable.
A set is countable if it each element can be associated with a natural number, because we
consider that natural numbers are infinite but yet they are countable. So, for a set to be
countable there is a one-to-one mapping between the elements of the set and natural
numbers. e.g. set of stars, set of integers.
Such mapping is not possible to set of all real numbers because between any two real
numbers there will be infinite real numbers and in that any two real numbers again infinite
real numbers and so on, so set of real numbers between 0 to 1/2 is not countable.
• Null set / empty set - Is the unique set having no elements. its size
or cardinality is zero i.e. |ɸ| = 0. It is denoted by a symbol ɸ or {}. A set with one
element is called singleton set.
• Universal set – if all the sets under investigation are subsets of a fixed set, i.e. the set
containing all objects, in venn diagram it is represented by a rectangle, and it is
denoted by U.
• Subset of a set – If every element of set A is also an element of set B i.e. ∀x(x ∈ A → x
∈ B), then A is called subset of B and is written as A ⊑ B. B is called the superset of A.
E.g. A = {1,2,3,4,5,6} B = {4,5,6}
• Note that to show that A is not a subset of B we need only find one element x ϵ A
with x ∉ B
• To show that A ⊑ B, show that if x ϵ A, then x ϵ B.

• ɸ ⊑ A Empty set ɸ is a subset for every set

• A ⊑ U every set is a subset of Universal set U
• A ⊑ A every set is a subset of itself.
• Proper subset – if A is a subset of B and A ≠ B, then A is said to be a proper subset of
B, i.e. there is at least one element in B which is not in A. denoted as A ⊂ B.
• Equality of sets – if two sets A and B have the same element and therefore every
element of A also belong to B and every element of B also belong to A, then the set A
and B are said to be equal and written as A=B. i.e. if A ⊑ B and B ⊑ A, then A=B. ∀x(x
∈ A ↔ x ∈ B)
 • Power set – let A be any set, then the set of all subsets of A is called power set of A
and it is denoted by P(A) or 2A. If A= {1,2,3}, then P(A) = {ɸ, {1}, {2}, {3}, [1,2}, {2,3},
{1,3}, {1,2,3}}
Cardinality of the power set of A is n, |P(A)|= 2n

• Sets can be represented graphically using Venn diagrams, named after the English
mathematician John Venn, who introduced their use in 1881. In Venn diagrams the
universal set U, which
• Contains all the objects under consideration, is represented by a rectangle. (Note
that the universal set varies depending on which objects are of interest.) Inside this
rectangle, circles or other geometrical figures are used to represent sets. Sometimes
points are used to represent the particular elements of the set. Venn diagrams are
often used to indicate the relationships between sets.

Q The cardinality of the power set of {0, 1, 2 . . ., 10} is _________. (GATE-2015) (1 Marks)
(A) 1024 (B) 1023 (C) 2048 (D) 2043
Answer: (C)

Q Which of the following are true?

1) ɸ ϵ A 2) ɸ ⊑ A 3) ɸ ϵ 2A 4) ɸ ⊑ 2A 5) A ϵ 2A 6) A ⊑ 2A

Q The power set of the set {Ф} is: (NET-Dec-2012)

a) {Ф} b) {Ф, {Ф}} c) {0} d) {0, Ф, {Ф}}
Answer: (b)

To understand this question better let’s try to understand it with another example
A={}
P(A) = {Ф}

A = {a}
P(A) = {Ф, {a}}

A = {a, b}
P(A) = {Ф, {a}, {b}, {a, b}}

A = {Ф}
P(A) = {Ф, {Ф}}
Q If ɸ is an empty set. Then | P(P(P(ɸ))) | =______?
a) 1 b) 2 c) 4 d) none of above
Ans: C

Q For a set A, the power set of A is denoted by 2A. If A = {5, {6}, {7}}, which of the following
options are True. (GATE-2015) (1 Marks)
I) ɸ ∈ 2A II) ɸ ⊑ 2A III) {5, {6}} ∈ 2A IV) {5, {6}} ⊑ 2A
(A) I and III only (B) II and III only (C) I, II and III only (D) I, II and IV only
Answer: (C)

Q The number of elements in the power set P(S) of the set S= {{∅},1, {2,3}} is: (GATE-1995)
(1 Mark)
a) 2 b) 4 c) 8 d) None of the above
Ans: C

Q let A be a set with n elements. Let C be a collection of distinct subsets of A such that for
any two subsets S1 and S2 in C, either S1 is subset of S2 or S2 is subset of S1. What is the
maximum cardinality of C? (GATE-2005) (2 Marks)
a) n b) n+1 c)2n-1+1 d) n!
Ans: b
 Operation on sets
• Complement of set – set of all x such that x ∉ A, but x ϵ U. Ac = {x | x ∉ A & x ϵ U}
• Union of sets – union of two sets A and B is a set of all those elements which either
belong to A or B or both, it is denoted by A U B. A U B = {x| x ϵ A or x ϵ B}

• Intersection of sets -- intersection of two sets A and B is a set of all those elements
which belong to both A and B, and is denoted by A ⋂ B. A ⋂ B = {x| x ϵ A and x ϵ B}

• Disjoint sets -- Two sets are said to be disjoint if they do not have a common
element, i.e. no element in A is in B and no element in B is in A. A ⋂ B = ɸ

• Set difference – the set difference of two sets A and B, is the set of all the elements
which belongs to A but do not belong to B. (A – B) / (A\B = {x| x ϵ A and x ∉ B}

• Symmetric difference – the symmetric difference of two sets A and B is the set of all
the elements that are in A or in B but not in both, denoted as.
o A ⨁ B = {A U B} -- {A ⋂ B}
 o A ⨁ B = {x| (x ϵ A and x ∉ B) or (x ϵ B and x ∉ A)}
o A ⨁ B = {A - B} U {B - A}

Q which of the following is not true?

a) A - B = A ⋂ Bc b) A - (A - B) = A ⋂ B
c) A - (A ⋂ B) = A - B d) A - (A - B) = B

Q If A ⊂ B, then which of the following is not true?

(a) A U B = B (b) A ⋂ B = A
C C
(c) B ⊂ A (d) B – A = ɸ

Q Which the following in not true?

a) If A ⊑ ɸ, then A = ɸ
b) (A ⋂ BC) U (A ⋂ B) = A
c) B U (A ⋂ B) = B
d) (A ⋂ BC) U (A ⋂ B) U (AC ⋂ B) U (AC ⋂ BC) = A ⋂ B

Q Which of the following is not true?

(a) (A - B) – C = A – (C – B)
(b) (A – B) – C = (A - C) – B
(c) (A - B) – C = A – (B ⋂ C)
(d) (A ⋂ B) – (B ⋂ C) = {A – (A⋂C)} – (A – B)

Q Let A, B and C be non-empty sets and let X = (A−B) −C and Y=(A−C) −(B−C). Which one of
the following is TRUE? (GATE-2005) (1 Marks)
a) X=Y b) X⊂Y c) Y⊂X d) None of these
Answer: (a)

Q Let A and B be sets and let Ac and Bc denote the complements of the sets A and B. the set
(a – b) ∪ (b - a) ∪ (a ∩ b) is equal to. (GATE- 1996) (1 Mark)
(a) A ∪ B (b) Ac ∪ bc (c) A ∩ B (d) Ac ∩ bc
Answer: (a)
Q If P, Q, R are subsets of the universal set U, then (GATE-2008) (1 Marks)
(P ⋂ Q ⋂ R) U (PC ⋂ Q ⋂ R) U QC U RC
(A) Qc U Rc (B) P U Qc U Rc
(C) Pc U Qc U Rc (D) U
Answer: (d)

Q let p, q and r be sets let @ denotes the symmetric difference operator defined as
P @ q = (p U q) – (p ∩ q)? (GATE-2006) (2 Mark)
I) p @ (q ∩ r) = (p @ q) ∩ (P @ q)
II) p∩ (q @ r) = (p ∩ q) @ (p @ r)
a) I only b) II only c) neither I nor II d) both I and II
Answer: (B)

Q Let E, F and G be finite sets.

Let X = (E ∩ F) – (F ∩ G) and Y = (E – (E ∩ G)) – (E – F).
Which one of the following is true? (GATE-2006) (2 Mark)
(A) X ⊂ Y (B) X ⊃ Y (C) X = Y (D) X – Y ≠ φ and Y – X ≠ φ
Answer: (C)

Q Let S be an infinite set S1, S2…………, Sn be Sets such that S1 U S2 U …U Sn = S Then, (GATE-
1993) (1 Marks)
(a) at least one of the set Si is a finite set
(b) not more than one of the set Si can be finite
(c) at least one of the sets Si is an infinite set
(d) not more than one of the sets Si can be infinite
Answer: (C)

Q Let P(S) denotes the power set of set S. Which of the following is always true? (GATE-
2000) (2 Marks)
(a) P(P(S)) = P(S) (b) P(S) ∩P(P(S)) = {φ}
(c) P(S) ∩S = P(S) (d) S ∉P(S)
Answer: (B)

Q In a class of 200 students, 125 students have taken Programming Language course, 85
students have taken Data Structures course, 65 students have taken Computer Organization
course; 50 students have taken both Programming Language and Data Structures, 35
students have taken both Data Structures and Computer Organization; 30 students have
taken both Data Structures and Computer Organization, 15 students have taken all the three
courses. How many students have not taken any of the three courses? (GATE-2004) (1 Mark)
(A) 15 (B) 20 (C) 25 (D) 35
Answer: (C)
P(AUBUC)=P(A)+P(B)+P(C)-P(A∩B)-P(A∩C)-P(B∩C)+P(A∩B∩C)
125+85+65-50−35−30+15=175
No of students not taking any courses-> 200−175=25

Q what is the cardinality of the set of integers X defined below (GATE-2006) (2 Mark)
X = {n| 1<=n<=123, n is not divisible by 2,3 or 5}?
a)28 b)33 c)37 d)44
Ans: b
N(AUBUC) = N(A) +N(B)+N(C) -N(A∩B)-N(B∩C)-N(A∩C)+ N(A∩B∩C)
61+41+24−20−12−8+4=90=61+41+24−20−12−8+4=90
123 −90 = 33

Q The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or
7 is ______. (GATE-2017) (1 Marks)
Ans: 271
166 + 100 + 71 -33-14-23+4 = 271

Q In a college, there are three student clubs, Sixty students are only in the Drama club, 80
students are only in the Dance club, 30 students are only in Maths club, 40 students are in
both Drama and Dance clubs, 12 students are in both Dance and Maths clubs, 7 students
are in both Drama and Maths clubs, and 2 students are in all clubs. If 75% of the students in
the college are not in any of these clubs, then the total number of students in the college is
_____________. (GATE-2019) (2 Mark)
(A) 1000 (B) 975 (C) 900 (D) 225
Answer: (C)
Therefore, total number of students participating in any of these clubs,
60 + 80 + 30 + 38 + 2 + 10 + 5
225
x*0.25 = 225
225/0.25

900

Q How many multiples of 6 are there between the following pairs of numbers? (NET-Jan-
2017)
0 and 100 and –6 and 34
a) 16 and 6 b) 17 and 6 c) 17 and 7 d) 16 and 7
Answer: (a)
Between 0 and 100 multiple of 6 are: 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96 ie.
16 multiple.
Between -6 and 34 multiple of 6 are: 0, 6, 12, 18, 24, 30. ie. 6 multiple.
So,option (a) is correct.

Q Consider a set A= {1,2, 3, ……...,1000}. How many members of A shall be divisible by 3 or

by 5 or by both 3 and 5? (NET-Dec-2014)
a) 533 b) 599 c) 467 d) 66
Answer: (C)

From set A numbers {3,6,9,……..999} which are divisible by 3 are 999 / 3 (A)= 333 .
From set A numbers {5,10,……995,1000} which are divisible by 5 are 1000 / 5 (B)= 200.
From set A numbers {15, 30, …990} which are divisible by 3 and 5 are 990 / 3 * 5 (A ∧ B)= 990 / 15 = 66.
So, numbers divisible by 3 or by 5 or by both 3 and 5:
(A ∨ B) = A + B – (A ∧ B)
(A ∨ B) = 333 + 200 – 67.
(A ∨ B) = 467.
So, option (C) is correct.

Q if Ai = {-i, …. -2, -1, 0, 1, 2, ….. i} (NET-July-2018)

then ⋃∞ 𝑖=1 𝐴𝑖 is
a) Z b) Q c) R d) C
Ans: b

Q Let A and B be sets in a finite universal set U. Given the following: |A – B|, |A ⊕ B|, |A| +
|B| and |A ∪ B| Which of the following is in order of increasing size? (NET-Dec-2016)
a) |A – B| < |A ⊕ B| < |A| + |B| < |A ∪ B|
b) |A ⊕ B| < |A – B| < |A ∪ B| < |A| + |B|
c) |A ⊕ B| < |A| + |B| < |A – B| < |A ∪ B|
d) |A – B| < |A ⊕ B| < |A ∪ B| < |A| + |B|
Ans: d

Q The power set of A U B, where A = {2, 3, 5, 7} and B = {2, 5, 8, 9} is (NET-Dec-2012)

a) 256 b) 64 c) 16 d) 4
Answer: (b)

A = {2, 3, 5, 7}, B = {2, 5, 8, 9} then A U B = {2, 3, 5, 7, 8, 9}

let A be any set, then the set of all subsets of A is called power set of A and it is denoted by
P(A) or 2A. If A= {1,2,3}, then P(A) = {ɸ, {1}, {2}, {3}, [1,2}, {2,3}, {1,3}, {1,2,3}}
If Cardinality of the power set of A is n, then |P(A)|= 2n
|A U B| = 6
|P(A U B)| = 26 = 64

Q Suppose U is the power set of the set S = {1,2,3,4,5,6}. For any T ∈ U, let |T| denote the
number of elements in T and T′ denote the complement of T. For any T, R ∈ U, let T\R be
the set of all elements in T which are not in R. (GATE-2015) (2 Marks)
Which one of the following is true?
A) ∀X∈U, (|X|=|X′|) B) ∃X∈U, ∃Y∈U, (|X|=5, |Y|=5 and X∩Y=ϕ)
C) ∀X∈U, ∀Y∈U, (|X|=2, |Y|=3 and X∖Y=ϕ) D) ∀X∈U, ∀Y∈U, (X ∖ Y= Y′ ∖ X′)
Ans: d

Q Consider the following statements:

S1: There exists infinite sets A, B, C such that A∩(B∪C) is finite.
S2: There exists two irrational numbers x and y such that (x + y) is rational.
Which of the following is true about S1 and S2? (GATE-2001) (2 Mark)
(a) Only S1 is correct (b) Only S2 is correct
(c) Both S1 and S2 are correct (d) None of S1 and S2 is correct
Ans: c

Q Consider the following relation on subsets of the set S of integers between 1 and 2014.
For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric
difference of the two sets is in U. Consider the following two statements: (GATE-2014) (2
Marks)
S1: There is a subset of S that is larger than every other subset.
S2: There is a subset of S that is smaller than every other subset.
Which one of the following is CORRECT?
(A) Both S1 and S2 are true (B) S1 is true and S2 is false
(C) S2 is true and S1 is false (D) Neither S1 nor S2 is true
Answer: (A)

Q 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:
I. Each compound in U \ S reacts with an odd number of compounds.
II. At least one compound in U \ S reacts with an odd number of compounds.
III. Each compound in U \ S reacts with an even number of compounds.
Which one of the above statements is ALWAYS TRUE? (GATE-2016) (2 Mark)
(A) Only I (B) Only II (C) Only III (D) None
Answer: (B)

Each compound in SS reacts with exactly 33 compounds in UU.

It means that the degree of every node(or compound) in SS is 33.
So sum of all the degree in S=S= number of nodes in S×S× degree of each node =9×3=27=9×3=27.
Now in U∖SU∖S we have 1414 nodes(or compounds), thus clearly U∖SU∖S contains an even number of
compounds.
Now if each compound in U∖SU∖S reacts with an even number of compounds, the sum of degrees of all
the node in U∖SU∖S would be even, and consequently, the sum of degrees of all the nodes in our
graph GGwould be odd as the sum of degrees of all the nodes in SS is odd, and an odd number added
with an even number produces an odd number.
But since in a graph, every edge corresponds to two degrees and the number of edges in a graph must
be a (non-negative)integral value & not fractional value hence the sum of the degrees all the nodes of a
graph must be even. (This is Handshaking Lemma).
So statement III should be false(always).

Q Let U = {1, 2, ..., n} and A = {(x, X), x ∈ X and X ⊆ U}. Consider the following two
statements for |A|. (Gate-2019) (1 Marks)
(i) |A| = n*2n−1
(ii) |A|= ∑𝑛𝑘=1 𝑘.nCr
Which of the following is correct?
(a) (i) only (b) (ii) only (c) Both (i) and (ii) (d) None of the above
Answer: (C)
Q The bit string for the sets, A = {1,3,5,7,9} and B = {1,2,3,4,5} are 1010101010 and
1111100000 respectively. If the universal set is U = {1, 2….,10} is represented 1111111111
which of the following is false?
a) A U B = 1111111010 b) A ⋂ B = 1010100000
c) A – B= 0000001010 d) AC = 0000011111
Ans: d

Q There are 100 people in a room. In this group 60 are men, 30 are young and 10 are young
men, then the number of old women is______?
a)12 b)20 c)30 d)80
Ans: b

Q how many possible integers are there that are <= 91 and are relatively prime to 91?
a)52 b)62 c)72 d)19
Ans: c
• Idempotent law
o AUA=A
o A⋂A=A

• Associative law
o (A U B) U C = A U (B U C)
o (A ⋂ B) ⋂ C= A ⋂ (B ⋂ C)

• Commutative law
o AUB=BUA
o A⋂B=B⋂A

• Distributive law
o A U (B ⋂ C) = (A U B) ⋂ (A U C)
o A ⋂ (B U C) = (A ⋂ B) U (A ⋂ C)

• De Morgan’s law
o (A U B) C = AC ⋂ BC
o (A ⋂ B) C = AC U BC

• Identity law
o AUɸ=A
o A⋂ɸ=ɸ
o AUU=U
o A⋂U=A

• Complement law
o A U AC = U
o A ⋂ AC = ɸ
o UC = ɸ
o ɸC = U

• Involution law
o ((A)C) C = A
 Cartesian Product

● Cartesian Product: - of two sets A and B in the set of all ordered pairs, whose first
member belongs to the first set and second member belongs to the second set,
denoted by A * B.
● It is a kind of maximum relation possible, where every member of the first set belong
to every member of the second set. A*B = {(a, b) | a ∈ A and b ∈ B}
● For E.g. if A = {a, b}, B = {1, 2, 3}, A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
● In general, commutative law does not hold good A* B != B*A
● If |A| = m and |B| = n then |A*B| = m.n

Q Let A be a finite set of size n. The number of elements in the power set of A×A is: (GATE-
1993) (1 Marks)
a) 2^(2^n) b) 2^(n^2) c) 2^n
d) 2^n e) None of the above
Answer: (B)
 Relation
● Relation: - Let A and B are sets then every subset of ‘A*B’ is called a relation from A
to B.
● If |A| =m and |B| = n then total no of element(pair) will be m*n, every element will
have two choice weather to present or not present in the subset(relation), therefore
the total number of relation possible is 2m.n.
● Largest relation possible will be A*B
● Smallest possible relation will be ɸ
● Complement of a relation: - Let R be a relation from A to B, then the complement of
relation will be denoted by R’, RC or R. R = {(a,b)|(a,b) ϵ A*B, (a,b) ϵ! R}
o R’ = (A*B) – R
o R U R’ = A*B
o R ⋂ R’ = ɸ
● For E.g. if A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}, R= {(a, 1), (a, 3), (b, 2)},
R’ = {(a, 2), (b, 1), (b, 3)}

● Inverse of a relation: - Let R be a relation from A to B, then the inverse of relation will
be a relation from B to A, denoted by R-1. R-1 = {(b, a) | (a, b) ∈ R}
● A*B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
● R = {(a, 1), (a, 3), (b, 2)}
● R-1 = {(1, a), (3, a), (2, b)}
● |R|=| R-1 |

Diagonal relation: - A relation R on a set A is said to be diagonal relation if, R is a set of all
ordered pair (x,x), for every ∀x ∈ A, sometimes it is also denoted by ▲A
R = {(x, x) | ∀ x ∈ A}

Q The number of binary relations on a set with n elements is: (GATE-1999) (1 Marks)
(A) n² (B) 2^n (C) 2^n² (D) None of the above
Answer: (C)
 Types of a Relation
• To further study types of relations, we consider a set A with n elements, then a
cartesian product A*A will have n2 elements(pairs). Therefore, total number of
relation possible is 2n * n

• Reflexive relation: - A relation R on a set A with cartesian product A*A is said to be

reflexive,
o If ∀ x ∈ A
o (x, x) ∈ R
• Smallest reflexive relation is ▲A
• Largest reflexive relation is A*A
• Total number of reflexive relations will be 2n(n-1)

Q What is the possible number of reflexive relations on a set of 5 elements? (GATE-2010) (1

Marks)
(A) 210 (B) 215 (C) 220 (D) 225
Answer: (C)

• Irreflexive relation: - A relation R on a set A with cartesian product A*A is said to be

Irreflexive,
o If ∀ x ∈ A
o (x, x) ∉ R
• Smallest irreflexive relation is ɸ
• Largest irreflexive relation is (A*A) - ▲A
• Total number of irreflexive relation will be 2n(n-1)

Q consider a set A = {1,2,3}, find which of the following relations are reflexive and
Irreflexive?
Relation Reflexive Irreflexive
A*A Yes No
ɸ No Yes
{(1,1), (2,2), (3,3)} Yes No
{(1,2), (2,3), (1,3)} No Yes
{(1,1), (1,2), (2,1), (2,2)} No No
{(1,1), (2,2), (3,3), (1,3), (2,1)} yes No
 {(1,3), (2,1), (2,3), (3,2)} no yes

If a relation R on a set A is reflexive, then RC is Irreflexive

• If two relations R1 and R2 are reflexive then their union and intersection will also be
reflexive.
• If two relations R1 and R2 are Irreflexive then their union and intersection will also be
Irreflexive.
Q Suppose that R1 and R2 are reflexive relations on a set A. Which of the following
statements is correct? (NET-July-2016)
a) R1 ∩ R2 is reflexive and R1 ∪ R2 is irreflexive.
b) R1 ∩ R2 is irreflexive and R1 ∪ R2 is reflexive.
c) Both R1 ∩ R2 and R1 ∪ R2 are reflexive.
d) Both R1 ∩ R2 and R1 ∪ R2 are irreflexive
Ans: c
Symmetric relation: - A relation R on a set A with cartesian product A*A is said to be
Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
then (b, a) ∈ R
……………………………
• If a relation on a set A is symmetric then R = R-1
• If two relations R1 and R2 are symmetric then their union and intersection will also
be symmetric.
• Smallest symmetric relation is ɸ
• Largest symmetric relation is A*A
• Total number of symmetric relation will be 2[n(n+1)]/2

Anti-Symmetric relation: - A relation R on a set A with cartesian product A*A is said to be

Anti-Symmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
(b, a) ∈ R
……………………………
a=b
……………………………
Conclusion: Symmetry is not allowed but diagonal pairs are allowed
• A relation R on a set A is Anti-Symmetric if (R ⋂ R-1) ⊑ ▲A
• Sub set of a Anti-Symmetric will also be Anti-Symmetric
• If two relations R1 and R2 are Anti - symmetric then their union need not to be Anti-
symmetric but intersection will also be Anti-symmetric.
• Smallest Anti-symmetric relation is ɸ
• Largest Anti-symmetric relation will contain n(n+1)/2 elements
• Total number of Anti-symmetric relation will be 2n *3[n(n-1)]/2
Asymmetric relation: - A relation R on a set A with cartesian product A*A is said to be
Asymmetric,
If ∀ a, b ∈ A
(a, b) ∈ R
……………………………
(b, a) ∉ R
……………………………
Conclusion: Symmetry is not allowed; even diagonal pairs are not allowed
Every asymmetric relation is also anti-symmetric
• Smallest Asymmetric relation is ɸ
• Largest Asymmetric relation will contain n(n-1)/2 elements
• Total number of Asymmetric relation will be 3[n(n-1)]/2

Relation Symmetric Anti-Symmetric Asymmetric

A*A Y N N
ɸ Y Y Y
{(1,1), (2,2), (3,3)} Y Y N
{(1,2), (2,3), (1,3)} N Y Y
{(1,1), (1,2), (2,1), (2,2)} Y N N
{(1,1), (2,2), (3,3), (1,3), (2,1)} N Y N
{(1,3), (2,1), (2,3), (3,2)} n n N

Q Consider a set A = {a, b, c} and R1, R2, R3 and R4 are relations on A which of the following
is not true?
Symmetric Anti-Symmetric Asymmetric
R1 = {(a, a), (c, c)} y Y T
R2 = {(a, b), (b, a), (a, c)} n N T
R2 = {(a, b), (b, c), (a, c)} n Y T
R2 = {(a, b), (b, a), (c, c)} y n T

Q Consider the binary relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}. Which one of
the following is TRUE? (GATE-2009) (1 Marks)
(A) R is symmetric but NOT antisymmetric
(B) R is NOT symmetric but antisymmetric
(C) R is both symmetric and antisymmetric
(D) R is neither symmetric nor antisymmetric
Answer: (D)

Q Let R be a relation on the set of ordered pairs of positive integers such that ((p, q), (r, s))
∈ R if and only if p–s = q–r. Which one of the following is true about R? (GATE-2015) (2
Marks)
(A) Both reflexive and symmetric
(B) Reflexive but not symmetric
(C) Not reflexive but symmetric
(D) Neither reflexive nor symmetric
Answer: (C)

Q How many relations are there on a set with n elements that are symmetric and a set with
n elements that are reflexive and symmetric? (NET-Dec-2012)
a) 2n(n+1)/2 and 2n.3n(n–1)/2 b) 3n(n–1)/2 and 2n(n–1)
C) 2n(n+1)/2 and 3n(n–1)/2 D) 2n(n+1)/2 and 2n(n–1)/2
Answer: (d)
Transitive relation: - A relation R on a set A with cartesian product A*A is said to be
Transitive,
If ∀ a, b ∈ A
(a, b) ∈ R
(b, c) ∈ R
……………………………
(a, c) ∈ R
……………………………
• Smallest Asymmetric relation is ɸ
• Largest Asymmetric relation will contain A*A elements
• If two relations R1 and R2 are Transitive then their union need not to be transitive
but intersection will also be transitive.

Relation Transitive
A*A Y
ɸ N
{(1,1), (2,2), (3,3)} Y
{(1,2), (2,3), (1,3)} y
{(1,1), (1,2), (2,1), (2,2)} y
{(1,1), (2,2), (3,3), (1,3), (2,1)} n
{(1,3), (2,1), (2,3), (3,2)} N
{(1,2)} y
{(1,3), (2,3)} Y
{(1,2), (1,3)} Y
{(2,3), (1,2)} n

|A| = n No of transitive relation

0 1
1 2
2 13
3 171
4 3994
 Warshall’s Algorithm
Q Consider a set A = {a, b, c, d} and a relation R = {(a, d), (b, a), (b, c), (c, a), (c, d), (d, c)}?
Q consider a set A = {1,2,3,4} and a relation R = {(1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2),
(3, 3), (3, 4)}?
Q Consider a set A = {1,2,3} and a relation R = {(1,1), (1,3), (2,2), (3,1), (3,2)}?
1 2 3
1 1 0 1
2 0 1 0
3 1 1

1 2 3
Column (1,3) (2,3) (1,3)
Row (1,3) (2) (1,2,3)
(1,1), (1,3), (3,1), (2,2), (3,2) (1,1), (1,2), (1,3),
(3,3) (3,1), (3,2), (3,3)

Q Let R be the relation on the set of positive integers such that a R b if and only if a and b
are distinct and have a common divisor other than 1. Which one of the following
statements about R is True? (GATE-2015) (1 Marks)
(A) R is symmetric and reflexive but not transitive
(B) R is reflexive but not symmetric and not transitive
(C) R is transitive but not reflexive and not symmetric
(D) R is symmetric but not reflexive and not transitive
Answer: (D)

Q A binary relation R on N x N is defined as follows:

(a, b) R (c, d) if a <= c or b <= d
Consider the following propositions:
P: R is reflexive
Q: R is transitive
Which one of the following statements is TRUE? (GATE- 2016) (2 Marks)
(A) Both P and Q are true. (B) P is true and Q is false.
(C) P is false and Q is true. (D) Both P and Q are false.
Answer: (B)
(4,7) (5,2)
(5,2) (1,3)
(4,7) (1,3)
Q The binary relation R= {(1,1), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (3,3), (3,4)} on the set A =
{1,2,3,4} is (GATE-1998) (2 Marks)
(a) reflexive, symmetric and transitive
(b) neither reflexive, nor irreflexive but transitive
(c) irreflexive, symmetric and transitive
(d) irreflexive and antisymmetric
Ans: b

Q The binary relation S = φ (empty set) on set A = {1,2,3} is (GATE-2002) (2 Marks)

(a) Neither reflexive nor symmetric (b) Symmetric and reflexive
(c) Transitive and reflexive (d) Transitive and symmetric
Ans d

Q The relation “divides” on a set of positive integers is ________. (NET-June-2013)

a) Symmetric and transitive b) Anti symmetric and transitive
c) Symmetric only d) Transitive only
Answer: (b)

Q A relation R in {1, 2,3,4,5,6} is given by {(1,2), (2,3), (3,4), (4,4), (4,5)}. This relation is:
(NET-Dec-2008)
a) Reflexive b) Symmetric
c) Transitive d) not reflexive, not symmetric and not transitive
Answer: (a)

0 1 0
Q the transitive closure of a relation R on a set A whose relation matrix 0 0 1 is: (NET-
1 0 0
June-2005)
0 1 0 1 1 0 1 1 1 0 1 1
a) 0 0 1 b) 1 1 0 c) 1 1 1 d) 0 1 1
1 0 0 1 1 0 1 1 1 0 1 1
Ans: c
Q The transitive closure of the relation {(1,2), (2,3), (3,4), (5,4)} on the set {1,2,3,4,5} is
___________. (GATE-1989) (2 Marks)
The transitive closure of the relation R = {(1,2),(2,3),(1,3) ,(3,4),(2,4),(1,4),(5,4)}
Equivalence Relation: - A relation R on a set A with cartesian product A*A is said to be
Equivalence, if it is
• Reflexive
• Symmetric
• Transitive

If two relations R1 and R2 are Equivalence then their union need not to be equivalence but
intersection will also be Equivalence.

Q Let R and S be any two equivalence relations on a non-empty set A. Which one of the
following statements is TRUE? (GATE-2005) (2 Marks)
(A) R ∪ S, R ∩ S are both equivalence relations
(B) R ∪ S is an equivalence relation
(C) R ∩ S is an equivalence relation
(D) Neither R ∪ S nor R ∩ S is an equivalence relation
Answer: (C)

Q Let R1 and R2 be two equivalence relations on a set. Consider the following assertions
(GATE-1998) (1 Marks)
(i) R1 U R2 is an equivalence relation
(ii) R1 ∩ R2 is an equivalence relation
Which of the following is correct?
a) Both assertions are true
b) Assertions (i) is true but assertions (ii) is not true
c) Assertions (ii) is true but assertions (i) is not true
d) Neither (i) nor (ii) is true
Answer: C

Q Consider the following relations:

R1 : (a, b) iff (a + b) is even over the set of integers
R2 : (a, b) iff (a + b) is odd over the set of integers
R3 : (a, b) iff a. b > 0 over the set of non-zero rational numbers
R4 : (a, b) iff |a – b| ≤ 2 over the set of natural numbers
Which of the following statements is correct? (GATE-2001) (1 Marks)
(a) R1 and R2 are equivalence relations, R3 and R4 are not
(b) R1 and R3 are equivalence relations, R2 and R4 are not
(c) R1 and R4 are equivalence relations, R2 and R3 are not
(d) R1, R2, R3 and R4 are all equivalence relations
Ans: b
Q Which of the relations on {0, 1, 2, 3} is an equivalence relation? (NET-July-2018)
a) {(0, 0) (0, 2) (2, 0) (2, 2) (2, 3) (3, 2) (3, 3)}
b) {(0, 0) (1, 1) (2, 2) (3, 3)}
c) {(0, 0) (0, 1) (0, 2) (1, 0) (1, 1) (1, 2) (2, 0)}
d) {(0, 0) (0, 2) (2, 3) (1, 1) (2, 2)}
Ans: b

Equivalence Class: - of an element is denoted by [x].

[x] = {y | y ∈ A and (x, y) ∈ R} for all x ∈ A
We can have [x] = [y], even if x != y

Q Consider A = {1, 2, 3, 4, 5} an equivalence relation R on A, R =

{(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,5),(5,2)} find the partition of a set A, defined by R.
[1] = {1, 4}
[2] = {2, 5}
[3] = {3}
[4] = {1,4}
[5] = {2, 5}

Partitions of a Set: - let A be a set, with n elements. Based on our understanding of

equivalent classes, a subdivision of A into non-empty and non-overlapping subset is called a
partition of A
A1 U A2 U A3 U ………….. U An = A
A1 ⋂ A2 ⋂ A3 ⋂ ………….. ⋂ An = ɸ

so we have partitions = {1, 4}, {2, 5}, {3}

Q Let A = {1,2,3,4,5} is a set having partitions as {1, 4}, {2, 3, 5} , find the equivalence
relation from which these partitions are created?
R = {(1, 4)* (1, 4), (2, 3, 5)* (2, 3, 5)}
R = {(1,1),(2,2),(3,3),(4,4),(5,5),(1,4),(4,1),(2,3),(3,2),(2,5),(5,2)(3,5)(5,3)}
Q A relation R is defined on the set of integers as x Ry iff (x + y) is even. Which of the
following statements is true? (GATE-2000) (2 Marks)
(a) R is not an equivalence relation
(b) R is an equivalence relation having 1 equivalence class
(c) R is an equivalence relation having 2 equivalence classes
(d) R is an equivalence relation having 3 equivalence classes
Answer: C
Q Let S be a set of n elements. The number of ordered pairs in the largest and the smallest
equivalence relations on S are (GATE-2007) (1 Marks)
(A) n and n (B) n2 and n (C) n2 and 0 (D) n and 1
Answer: (B)

Q Suppose A is a finite set with n elements. The number of elements in the largest
equivalence relation of A is? (GATE-1998) (1 Marks)
(a) n (b) n2 (c) 1 (d) n + 1
Ans: c

Q Let R be a non-empty relation on a collection of sets defined by A R B if and only if A ∩ B

= φ. Then, (pick the true statement) (GATE-1996) (2 Marks)
(a) R is reflexive and transitive (b) R is symmetric and not transitive
(c) R is an equivalence relation (d) R is not reflexive and not symmetric
Ans: b

Q How many different equivalence relations with exactly three different equivalence
classes are there on a set with five elements? (NET-July-2016)
(A) 10 (B) 15 (C) 25 (D) 30
Answer: (C)

Q The number of equivalence relations of the set {1,2,3,4} is (GATE-1997) (1 Marks)

a) 15 b) 16 c) 24 d) 4
Answer: (A)

Q “x^1 is a clone of x” means x^1 is identical to x in terms of the physical attributes namely,
height, weight and complexion. Given, height, weight and complexion only form a complete
set of attributes for an entity, cloning is an equivalence relation. What is your impression
about this statement? (NET-June-2010)
a) The statement is true b) The statement is false
c) The truth value of the statement cannot be computed d) None of these
Answer: (a)
Partial Order Relation: - A relation R on a set A with cartesian product A*A is said to be
partial order, if it is
• Reflexive
• Anti - Symmetric
• Transitive
Partial ordering set (Poset): - a set A with partial ordering relation R defined on A is called a
POSET and is denoted by [A; R]
For e.g. [A, /], [A, <=], [P(S), ⊑]
Total order relation: - A Poset [A; R] is called a total order set, if every pair of elements are
comparable i.e. either (a, b) or (b, a) x ∈ R, for ∀ a, b ∈ A
For e.g. A = {1, 2, 3, 6}, then Poset [A,/] is not a total order relation but A = {1248} will be

Q A relation R is defined on ordered pairs of integers as follows: (x, y) R (u, v) if x < u and y >
v. Then R is (GATR-2006) (1 Marks)
(A) Neither a Partial Order nor an Equivalence Relation
(B) A Partial Order but not a Total Order
(C) A Total Order
(D) An Equivalence Relation
Answer: A

Q let R1 be a relation from A = {1,3,5,7} to B = {2,4,6,8} and R2 be another relation from B to

C = {1,2,3,4} as defined below (GATE-2004) (1 Marks)
(i) an element x in A is related to an element y in B if x + y is divisible by 3
(ii) an element x in B is related to an element y in C if x + y is even but not divisible by 3.
Which is the composite relation R1R2 from A to C?
a) {(1,2), (1,4), (3,3), (5,4), (7,3)} b) {(1,2), (1,3), (3,2), (5,2), (7,3)}
c) {(1,2), (3,2), (3,4), (5,4), (7,2)} d) {(3,2), (3,4), (5,1), (5,3), (7,1)}
Answer: C
Q Which of the following statements is true? (NET-July-2018)
a) (Z, ≤) is not totally ordered
b) The set inclusion relation ⊆ is a partial ordering on the power set of a set S
c) (Z, ≠) is a Poset

d) The directed graph is not a partial order

Ans: b
Q Let R be a symmetric and transitive relation on a set A. Then (GATE-1995) (1 Marks)
a) R is reflexive and hence an equivalence relation
b) R is reflexive and hence a partial order
c) R is reflexive and hence not an equivalence relation
d) None of the above
Answer: (D)

Q A partial order P is defined on the set of natural numbers as follows. Here x/y denotes integer division.
(GATE-2007) (2 Marks)
(1) (0,0) ∈ P (2) (a, b) ∈ P if and only if a % 10 <= b % 10 and (a/10, b/10) ∈ P.
Consider the following ordered pairs:
(i) (101,22) (ii) (22,101) (iii) (145,265) (iv) (0,153)
a) I & iii b) ii & iv c) I & iv d) iii & iv
Ans : d
 Conversion of poset into a Hasse Diagram
If we want to study Partial order relation further then it will be better to convert it into
more convinent notation so that it can be studied easily. This graphical representation is
called Hasse Diagram
Stepts to convert partial order relation into hasse diagram
1- Draw a vertex for each element in the Set
2- If (a,b) ϵ R then draw an edge from a to b
3- Remove all Reflexive and Transitive edges
4- Remove the direction of edges and arrange them in the increasing order of heights.
Q Consider a Partial order relation and convert it into hasse diagram?
R = {(1,1), (1,2), (1,4), (1,8), (2,2), (2,4), (2,8), (4,4), (4,8), (8,8)}

Q Consider a Partial order relation and convert it into hasse diagram?

R = {(1,1), (1,2), (1,3), (1,6), (2,2), (2,6), (3,3), (3,6), (6,6)}
Q Study the follwing hasse diagram and find which of the follwing are valid?
Conclusion
• We can not have a horizontal edge in a hasse diagram
• We can not have a reflexive and transativie edge in Hasse Diagram

Q Let X = {2,3,6,12,24}, Let ≤ be the partial order defined by X ≤ Y if x divides y. Number of

edges as in the Hasse diagram of (X, ≤) is. (GATE-1996) (1 Marks)
(a) 3 (b) 4 (c) 9 (d) None of the above
Ans b
 Elements of a Poset
Maximal Element: - An element is said to be maximal if it is not related to any other
element in the Partial order relation.
Minimal Element: - An element is said to be minimal if no other element is related to it in
the Partial order relation.
• Every hasse diagram will have at least one Maximal and Minimal element(one or
more).
Maximum/Greatest Element: - An element is said to be Maximum/Greatest if it is not
related to any other element but every element is related to it in Partial order relation. Or if
a hasse diagram has only one Maximal element then it will also be Maximum/Greatest
element.
Minimum/Least Element: - An element is said to be Minimum/Least if no other element is
related to it but it is related to every element Partial order relation. Or if a hasse diagram
has only one Minimal element then it will also be Minimum/Least element.
• Every hasse diagram will have at most one Greatest and Least element(zero or one).
• Every Greatest element is also Maximal
• Every Least element is also Minimal
Upper Bound: - Upper bound of a subset B with respect to set A, will contain all
those element to which all the elements of B is related.
Lower Bound: - lower bound of a subset B with respect to A, will contain all
those elements which are related to every element of B.
Least Upper Bound/LUB/Join/Supremeum/∨: - Least value in the upper bpund
Greatest Lower Bound/GLB/Meet/Infimum/∧: - Greatest value in the lower bound

Q Consider the Poset ({3,5,9,15,24,45}, /). Which of the following is correct for the given
Poset? (NET-JUNE-2019)
a) There exist a greatest element and a least element
b) There exist a greatest element but not a least element
c) There exist a least element but not a greatest element
d) There does not exist a greatest element and a least element
Ans: d
 Lattice
Join Semi Lattice :- A hasse diagram/Partial order relation is called Join Semi Lattice if for
every elements their exists a Join.
Meet Semi Lattice :- A hasse diagram/Partial order relation is called Meet Semi Lattice if for
every elements their exists a Meet.
Lattice :- A hasse diagram/Partial order relation is called Lattice if their exist a Join and
Meet for every pair of element. Or A hasse diagram/Partial order relation is called Latice if
it is both Join Semi Lattice and Meet Semi Lattice.

Q Which of the following elements are lattice ?

Q A partially ordered set is said to be a lattice if every two elements in the set have (NET-
Dec-2010)
a) a unique least upper bound b) a unique greatest lower bound
c) both (A) and (B) d) none of the above
Answer: (C)

Q the inclusion of which of the following set into S = {{1,2},{1,2,3},{1,3,5},{1,2,4},{1,2,3,4,5}}

is necessary and sufficient to make S a complete lattice under the partial order defined by
set containment? (GATE-2004) (2 Marks)
a) {1} b) {1}, {2,3} c) {1}, {1,3} d) {1}, {1,3}, {1,2,3,4}, {1,2,3,5}
Ans: a
Q Consider the following Hasse diagrams

Which all of the above represent a lattice? (GATE-2008) (2 Marks)

(A) (i) and (iv) only (B) (ii) and (iii) only
(C) (iii) only (D) (i), (ii) and (iv) only
Answer: (A)

Q Consider the set X={a, b, c, d, e} under partial

ordering R={(a,a),(a,b),(a,c),(a,d),(a,e),(b,b),(b,c),(b,e),(c,c),(c,e),(d,d),(d,e),(e,e)}. The Hasse
diagram of the partial order (X, R) is shown below.

The Hasse diagram of the partial order (X, R) is shown below.

The minimum number of ordered pairs that need to be added to RR to make (X, R) a lattice
is ______ (GATE-2017) (1 Marks)
Answer: 0
 Boolean algebra
Unbounded Lattice :- If a lattice has infinite of elements then it is called
Unbounded Lattice.

Bounded Lattice :- If a lattice has finite number of elements then it is called

Bounded lattice, there will be upper and lower bound in lattice.
Complement of an element in a Lattice :- If two elements a and ac, are complement
of each other, then the following equations must always holds good.
a ∨ ac = Upper bound of lattice
a ∧ ac = Lower bound of lattice
Distributive Lattice :- A lattice is said to be distributted lattice. if for every element
their exist at most one element(zero or one).
Complement Lattice :- A Lattice is said to be Complement lattice. if for every
element their exist at least one element(one or more).
Boolean Algebra :- A Lattice is said to be Boolean Algebra, if for every element
their exist exactly one complement. Or if a lattice is both complemented and
distributed then it is called Boolean Algebra.
Q The complement(s) of the element 'a' in the lattice shown in below figure is (are) ____
(GATE-1988) (2 Marks)

Q the relation <= and < om a Boolean algebra is defined as :

x<=y if and only if x ∨ y =y
x<y means x<=y but x!=y
x>=y means y<=x and
x>y means y<x
considering the above definitions, which of the following in not true in the Boolean
algebra?
1) if x<=y and y<=z, then x<=z 2) if x<=y and y<=x, then x=y
3) if x<y and y<z, then x<=y 4) if x<y and y<z, then x<y
a)2 and 3 b)3 c)1 and 2 d) 4
(NET-Dec-2018)

Q The following is the Hasse diagram of the Poset [{a, b, c, d, e}, ≤]

The Poset is (GATE-2005) (1 Marks)
(A) not a lattice (B) a lattice but not a distributive lattice
(C) a distributive lattice but not a Boolean algebra (D) a Boolean algebra
Answer: (B)

Q Find which of the following is a lattice and Boolean Algebra?

1) [D12, /]
2) [{1,2,3,4,6,9}, /]
3) [{2,3,4,6,12}, /]
4) [{1,2,3,5,30}, /]
5) [{1,2,3,6,9,18}, /]
6) [D110, /]
7) [D45, /]
8) [{2,3,4,9,12,18}, /]
9) [R, <=]
10) [D81, /]
11) [D30, /]
12) [D64, /]
13) [D10, /]
14) [D91, /]
15) [D10, /]
16) [P(A), ⊑], A = {1,2,3}
Q Consider the following hasse diagram, find which of the following is true?
a) it is a lattice b) subset {a,b,c,d} is a lattice
c) subset {b,c,d,e} is a lattice d) subset {a,b,c,e} is a lattice

Q Consider the following hasse diagram, find which of the following is true?

a) subset {a,b,c,g} is a lattice b) subset {a,b,f,g} is a lattice

c) subset {a,d,e,g} is a lattice d) subset {a,c,e,g} is a lattice
 Proposition
• First understand the difference between Scientist and Philosopher. Philosopher give an
idea or theory which may have different interpretation from person to person. It depends
on the wisdom of a person.
• There are different philosophers in the world suggested different philosophy like, Plato,
Aristotle, Confucius, Karl Marx, Laozi, Chanakya, Mahatma Gandhi, Gautam Buddha
• Proposition with rules of logic actually is a method of reasoning (unambiguous, machinic,
deterministic), given by Aristotle who was the teacher of Alexander son of King Philip of
Macedonia and there may be different methods of solving a problem apart from
proposition.
• Proposition and rules of logic specify the meaning of mathematical statements. Logic is
the basis of all mathematical reasoning, and of all automated reasoning. It has practical
applications to the design of computing machines, to the specification of systems, to
artificial intelligence, to computer programming, to programming languages, and to other
areas of computer science, as well as to many other fields of study.
• To understand mathematics, we must understand what makes up a correct mathematical
argument, that is, a proof. Once we prove a mathematical statement is true, we call it a theorem.
A collection of theorems on a topic organize what we know about this topic.
•
• Everyone knows that proofs are important throughout mathematics, even in computer science.
In fact, proofs are used to verify that computer programs produce the correct output for all
possible input values, to show that algorithms always produce the correct result, to establish the
security of a system, and to create artificial intelligence.
• The rules of logic give precise meaning to mathematical statements. These rules are used to
distinguish between valid and invalid mathematical arguments.

• The area of logic that deals with propositions is called the propositional calculus or
propositional logic or predicate calculus (study of propositions). It was first developed
systematically by the Greek philosopher Aristotle more than 2300 years ago.
• We now turn our attention to methods for producing new propositions from those
that we already have. These methods were discussed by the English mathematician
George Boole in 1854 in his book The Laws of Thought.
If a set of Premises(P) yield another proposition Q(Conclusion), then it is called an Argument
and it is denoted by
{P1, P2, P3..., PN} |- Q

P1
P2
P3
.

.
PN
……
Q
…….

{P1 ∧ P2 ∧ P3 ∧.... ∧ PN} |- Q

An argument is said to be valid if the conclusion Q can be derived from the premises by
applying the rules of inference. Premises is a statement that provides reason or support for
the conclusion.
A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either
true or false, but not both.
For e.g.
• Delhi is the capital of USA
• How are you doing
• 5<= 11
• Temperature is less than 10 C
• It is cold today
• Read this carefully
• X+y=z
• Law of contradiction - the law of non-contradiction (LNC) (also known as the law of
contradiction, principle of non-contradiction (PNC), or the principle of contradiction)
states that contradictory propositions cannot both be true in the same sense at the same
time. e.g. the two propositions "A is B" and "A is not B" are mutually exclusive.

• Law of excluded middle - the law of excluded middle (or the principle of excluded middle)
states that for any proposition, either that proposition is true or its negation is true.
•

Types of proposition
We use letters to denote propositional variables (or statement variables), that is, variables
that represent propositions, just as letters are used to denote numerical variables. The
conventional letters used for propositional variables are p, q, r, s. The truth value of a
proposition is true, denoted by T, if it is a true proposition, and the truth value of a
proposition is false, denoted by F, if it is a false proposition.
Many mathematical statements are constructed by combining one or more propositions.
New propositions, called compound propositions, are formed from existing propositions
using logical operators.

Operators / Connectives
Negation: - let p be a proposition. The negation of p, denoted by ¬p, is the statement “it is
not the case that p”.
The truth value of the negation of p, ¬p, is the opposite of the truth value of p.
e.g. “Michael’s PC runs Linux” = “It is not the case that Michael’s PC runs Linux.” = “Michael’s
PC does not run Linux.”
“Vandana’s smartphone has at least 32GB of memory” = “It is not the case that Vandana’s
smartphone has at least 32GB of memory.” = “Vandana’s smartphone does not have at least
32GB of memory” = “Vandana’s smartphone has less than 32GB of memory.”

Negation
P ¬P
F T
T F
The negation operator constructs a new proposition from a single existing proposition.
 Conjunction
• Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q, is the proposition
“p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

Conjunction
p q p∧q
F F F
F T F
T F F
T T T

• e.g. p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is
the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”
• The conjunction of , p q, is the proposition “Rebecca’s PC has more than 16 GB free hard disk
space, and the processor in Rebecca’s PC runs faster than 1 GHz.” This conjunction can be
expressed more simply as “Rebecca’s PC has more than 16 GB free hard disk space, and its
processor runs faster than 1 GHz.”

¬ (p ∧ q) ¬ (p ∧ q)
p q
¬q ¬p

(p ∧ q) P
p p∧q

¬ (p ∧ q) ¬ (p ∧ q)
¬p ¬p
q ¬q

P
q
p∧q
 Disjunction
• Let p and q be propositions. The disjunction of p and q, denoted by p ∨ q, is the
proposition. “p or q.” The disjunction p ∨ q is false when both p and q are false and is true
otherwise.

Disjunction
p q p∨q
F F F
F T T
T F T
T T T

(p ∧ q) (p ∨ q)
(p ∨ q) (p ∧ q)

(p ∨ q) (p ∨ q)
¬p ¬q
q p

(p ∨ q) (p ∨ q)
p p
¬q q

¬ (p ∨ q) (p ∨ q)
¬p p

P
p∨q
 XOR(Exclusive-OR)
• When the exclusive or is used to connect the propositions p and q, the proposition “p or q
(but not both)” is obtained. This proposition is true when p is true and q is false, and when
p is false and q is true, denoted by p ⊕ q. It is false when both p and q are false and when
both are true.

XOR(Exclusive-OR)

p q p⊕q
F F F
F T T
T F T
T T F

(p ⊕ q) (p ∨ q)
(p ∨ q) (p ⊕ q)

(p ⊕ q) (p ⊕ q)
p ¬p

¬ (p ∨ q) (p ∧ q)
(p ⊕ q) (p ⊕ q)
 Implication
• Let p and q be propositions. The conditional statement p → q is the proposition “if p,
then q”. The conditional statement p → q is false when p is true and q is false, and true
otherwise.
• Conditional statement p → q is called the hypothesis (or antecedent or premise) and q
is called the conclusion. The statement p → q is called a conditional statement because
p → q asserts that q is true on the condition that p holds. A conditional statement is
also called an implication.

Implication

p q p→q

F F T

F T T

T F F

T T T

“if p, then q” “p implies q” “if p, q” “p only if q” “p is sufficient for q”

“a sufficient condition for q is p” “q if p” “q whenever p” “q
when p” “q is necessary for p” “a necessary condition for p is q” “q follows
from p” “q unless ¬p”

e.g. Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria
will find a good job.” Express the statement p → q as a statement in English.
“If Maria learns discrete mathematics, then she will find a good job.” = “Maria will find a
good job when she learns discrete mathematics.” = “For Maria to get a good job, it is
sufficient for her to learn discrete mathematics.” = “Maria will find a good job unless she
does not learn discrete mathematics.”
p → q implication
q → p converse
¬p → ¬q inverse
¬q → ¬p contra positive
p → q = ¬q → ¬p
p → q will be true if either p is false or q is true, p → q = ¬p ∨ q
Modus Modus
Ponens Tollens
p →q p →q
p ¬q
q ¬p

¬p q
p →q p →q

¬ (p → q) ¬ (p → q)
¬q p
 Bi-conditional
Let p and q be propositions. The biconditional statement p ↔ q is the proposition “ p if
and only q”. the biconditional statement p ↔ q is true when p and q have the same values,
and false otherwise. Biconditional statements are also called bi-implications.

“p is necessary and sufficient for q”

“if p then q, and conversely”
“p iff q.”

p←→ q = (p → q ) ∧ ( q → p)

Implication
p q P↔q
F F T
F T F
T F F
T T T
Q Find which of the following argument is valid?
p →q
q →r p →r P
p →r q →s Q
¬r ∨ ¬s r
¬p ∨ ¬q
p ∨q
p →r
q →r
r
P
q ¬p
p ∨q q
p →r
q →s
r ∨s
 Type of cases
Tautology/valid: - A propositional function which is always having truth in the last column, is
called tautology. E.g. p ∨ ¬ p

p ¬p p ∨ ¬p
F T T
T F T

Contradiction/ Unsatisfiable: - A propositional function which is always having false in the

last column, is called Contradiction. E.g. p ∧ ¬ p

p ¬p p ∧ ¬p
F T F
T F F

Contingency: - A propositional function which is neither a tautology nor a contradiction, is

called Contingency. E.g. p ∨ q

p q p∨q
F F F
F T T
T F T
T T T

Satisfiable: - A propositional function which is not contradiction is satisfiable. i.e. it must

have at least one truth value in the final column e.g. p ∨ q

Functionality Complete Set: - A set of connectives is said to be functionally complete if it is

able to write any propositional function.

{∧, ¬}
{∨, ¬}

Q consider the following argument

I1: if today is Gandhi ji’s birthday, then today is oct 2nd
I2: today is oct 2nd
C: today is Gandhi ji’s birthday
Q consider the following argument
I1: if Canada is a country, then London is a city
I2: London is not a city
C: Canada is not a country

Q What is the converse of the following assertion? (GATE-2001) (1 Marks)

I stay only if you go.
(A) I stay if you go (B) If I stay then you go
(C) If you do not go then I do not stay (D) If I do not stay then you go
Answer: (A)

Q Consider the following logical inferences.

I1: If it rains then the cricket match will not be played.
The cricket match was played.
Inference: There was no rain.
I2: If it rains then the cricket match will not be played.
It did not rain.
Inference: The cricket match was played.
Which of the following is TRUE? (GATE-2012) (1 Marks)
(A) Both I1 and I2 are correct inferences
(B) I1 is correct but I2 is not a correct inference
(C) I1 is not correct but I2 is a correct inference
(D) Both I1 and I2 are not correct inferences
Answer: (B)

Q Consider the following statements:

P: Good mobile phones are not cheap
Q: Cheap mobile phones are not good
L: P implies Q
M: Q implies P
N: P is equivalent to Q
Which one of the following about L, M, and N is CORRECT? (GATE-2014) (1 Marks)
(A) Only L is TRUE. (B) Only M is TRUE.
(C) Only N is TRUE. (D) L, M and N are TRUE
Answer: (D)

Q Consider the following logical inferences: (NET-Aug-2016)

I1: If it is Sunday then school will not open. The school was open.
Inference: It was not Sunday.
I2: If it is Sunday then school will not open. It was not Sunday.
Inference: The school was open.
Which of the following is correct?
A) Both I1 and I2 are correct inferences.
B) I1 is correct but I2 is not a correct inference.
C) I1 is not correct but I2 is a correct inference.
D) Both I1 and I2 are not correct inferences.
Ans. B

Q Consider the following two statements.

S1: If a candidate is known to be corrupt, then he will not be elected.
S2: If a candidate is kind, he will be elected.
Which one of the following statements follows from S1 and S2 as per sound inference rules
of logic? (GATE-2015) (1 Marks)
(A) If a person is known to be corrupt, he is kind
(B) If a person is not known to be corrupt, he is not kind
(C) If a person is kind, he is not known to be corrupt
(D) If a person is not kind, he is not known to be corrupt
Answer: (C)

Q Which of the following arguments are not valid? (NET-Dec-2015)

(a) “If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion,
then he will be happy. He will not be happy, therefore, either he will not get the job or he will
not work hard”.
(b) “Either Puneet is not guilty or Pankaj is telling the truth. Pankaj is not telling the truth,
therefore, Puneet is not guilty”.
(c) If n is a real number such that n>1, then n2>1. Suppose that n2>1, then n>1.
Codes:
A) (a) and (c) B) (b) and (c) C) (a), (b) and (c) D) (a) and (b)
Ans. B

Q “If my computations are correct and I pay the electric bill, then I will run out of money. If I
don’t pay the electric bill, the power will be turned off. Therefore, if I don’t run out of money
and the power is still on, then my computations are incorrect.” Convert this argument into
logical notations using the variables c, b, r, p for propositions of computations, electric bills,
out of money and the power respectively. (Where ¬ means NOT) (NET-June-2015)
A) if (c Λ b) → r and ¬b → p, then (¬r Λ p) → ¬c
B) if (c ∨ b) → r and ¬b → ¬p, then (r Λ p) → c
C) if (c Λ b) → r and ¬p → b, then (¬r ∨ p) → ¬C
D) if (c ∨ b) → r and ¬b → ¬p, then (¬r Λ p) → ¬c
Ans. A

Q In Propositional Logic, given P and P → Q, we can infer __________. (NET-June-2015)

a) ~ Q b) Q c) P ∧ Q d) ~ P ∧ Q
Ans. B

Q The proposition ~ p ∨ q is equivalent to (NET-Dec-2011)

(A) p → q (B) q → p (C) p ↔ q (D) p ∨ q
Ans: a

Q the Preposition (p → q) ∧ (¬q ∨ p) is equivalent to: (NET-June-2006)

a) q →p b) p → q c) (q → p) ∨ (p → q) d) (p → q) ∨ (q → p)

Q Let P and Q be two propositions, ¬ (P ↔ Q) is equivalent to: (NET-Jan-2017)

(I) P ↔ ¬ Q (II) ¬ P ↔ Q (III) ¬ P ↔ ¬ Q (IV) Q → P
A) Only (I) and (II) B) Only (II) and (III)
C) Only (III) and (IV) D) None of the above
Ans. A

Q In propositional logic P ↔ Q is equivalent to (Where ~ denotes NOT) (NET-June-)

a) ~(P ∨ Q) ∧ ~(Q ∨ P) b) (~P ∨ Q) ∧ (~Q ∨ P)
c) (P ∨ Q) ∧ (Q ∨ P) d) ~(P ∨ Q) → ~ (Q ∨ P)
Ans. B

Q the statement (¬p) ⟹ (¬q) is logically equivalent to which of the statement below? (GATE-
2017) (1 Marks)
1) p ⟹ q 2) q ⟹ p 3) (¬q) ∨ (p) 4) (¬p) ∨ q
a) 1 only b) 1 and 4 only c) 2 only d) 2 and 3 only
Answer: (D)

Q The Boolean function [~(~p ∧ q) ∧ ~( ~p ∧ ~q)] ∨ (p ∧ r)] is equal to the Boolean function:
(NET-Aug-2016)
a) q b) p ∧ r c) p ∨ q d) p
Ans. D
Q The first order logic (FOL) statement ((R ∨ Q) ∧ (P ∨ ¬Q)) is equivalent to which of the
following? (NET-Jan-2017)
A) ((R ∨ ¬Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P)) B) ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ P))
C) ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (R ∨ ¬P)) D) ((R ∨ Q) ∧ (P ∨ ¬Q) ∧ (¬R ∨ P))
Ans. B
Q An example of a Tautology is: (NET-June-2008)
a) x ∨ y b) x ∨ ¬y c) x ∨ ¬x d) (x → y) ∧ (y → x)

Q Which one of the following is NOT equivalent to p ↔ q? (GATE-2015) (1 Marks)

a) (¬p ∨ q) ∧ (p ∨ ¬q) b) (¬p ∨ q) ∧ (q → p)
c) (¬p ∧ q) ∨ (p ∧ ¬q) d) (¬p ∧ ¬q) ∨ (p ∧ q)
Answer: (C)

Q P and Q are two propositions. Which of the following logical expressions are equivalent?
(GATE-2008) (2 Marks)
A) P ∨ ¬Q B) ¬(¬P ∧ Q)
C) (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ ¬Q) D) (P ∧ Q) ∨ (P ∧ ¬Q) ∨ (¬P ∧ Q)
(A) Only I and II (B) Only I, II and III
(C) Only I, II and IV (D) All of I, II, III and IV
Answer: (B)

Q Which one of the following Boolean expressions is NOT a tautology? (GATE-2014) (2

Marks)
A) ((a → b) ∧ (b → c)) → (a → c) B) (a → c) → (∼b → (a ∧ c))
C) (a ∧ b ∧ c) → (c ∨ a) D) a → (b → a)
Answer: (B)

Q The proposition p ∧ (∼p ∨ q) is: (GATE-1993) (1 Marks)

a) a tautology b) logically equivalent to p ∧ q
c) logically equivalent to p ∨ q d) a contradiction
e) none of the above
Answer: (B)

Q If the proposition ¬p → q is true, then the truth value of the proposition ¬p ∨ (p → q),
where ¬ is negation, ∨ is inclusive OR and → is implication, is (NET-dec-2005)
a) True b) Multiple Values c) False d) Cannot be determined
Ans: d

Q Consider the compound propositions given below as: (NET-Dec-2015)

(a) p ∨ ~ (p ∧ q) (b) (p ∧ ~q) ∨ ~(p ∧ q) (c)p ∧ (q ∨ r)
Which of the above propositions are tautologies?
A) (a) and (c) B) (b) and (c) C) (a) and (b) D) only (a)
Ans. D
Q Let p, q, and r be the propositions and the expression (p -> q) -> r be a contradiction. Then,
the expression (r -> p)-> q is (GATE-2017) (2 Marks)
(A) a tautology (B) a contradiction
(C) always TRUE when p is FALSE (D) always TRUE when q is TRUE
Answer: (D)

Q Let P, Q, R and S be Propositions. Assume that the equivalences P ⇔ (Q ∨ ¬ Q) and Q ⇔ R

hold. Then the truth value of the formula (P ∧ Q) ⇒ ((P ∧ R) ∨ S) is always: (NET-Jan-2017)
A) True B) False C) Same as truth table of Q D) Same as truth table of S
Ans. A

Q consider the following expression: (GATE-2016) (1 Marks)

i) false ii) Q iii) true iv) P ∨ Q v) ¬Q ∨ P
The number of expressions given above that are logically implied by P ∧ (P ⟹ Q) is___
Answer: 4

Q Let p, q, r, s represents the following propositions. (GATE-2016) (1 Marks)

• p: x ∈ {8, 9, 10, 11, 12}

• q: x is a composite number
• r: x is a perfect square
• s: x is a prime number

The integer x≥2 which satisfies ¬((p ⇒ q) ∧ (¬r ∨ ¬s)) is ____________.

Answer: 11

Q In propositional logic if (P → Q) ∧ (R → S) and (P ∨ R) are two premises such that

(P → Q) ∧ (R → S)
P∨R
…….
Y
…….
is the premise: (NET-Jan-2017)
A) P ∨ R B) P ∨ S C) Q ∨ R D) Q ∨ S
Ans. D

Q Indicate which of the following well-formed formulae are valid: (GATE-1990) (2 Marks)
a) [(P ⇒ Q) ∧ (Q ⇒ R)] ⇒ (P ⇒ R) b) (P ⇒ Q) ⇒ (¬P ⇒ ¬Q)
c) (P ∧ (¬P ∨ ¬Q)) ⇒ Q d) (P ⇒ R) ∨ (Q ⇒ R) ⇒ ((P ∨ Q) ⇒ R)
Answer: (A)
Q Consider two well-formed formulas in propositional logic
F1:P⇒¬P F2:(P⇒¬P) ∨ (¬P⇒P)
Which one of the following statements is correct? (GATE-2001) (1 Marks)
A) F1 is satisfiable, F2 is valid B) F1 unsatisfiable, F2 is satisfiable
C) F1 is unsatisfiable, F2 is valid D) F1 and F2 are both satisfiable
Answer: (A)

Q Consider the following two well-formed formulas in prepositional logic.

F1: P ⇒ ¬ P
F2: (P ⇒ ¬ P) ∨ (¬ P ⇒ P)
Which of the following statements is correct? (NET-Jan-2017)
A) F1 is Satisfiable, F2 is valid B) F1 is unsatisfiable, F2 is Satisfiable
C) F1 is unsatisfiable, F2 is valid D) F1 and F2 both are Satisfiable
Ans. A

Q The following propositional statement is (GATE-2004) (2 Marks)

(P → (Q v R)) → ((P ^ Q) → R)
(A) satisfiable but not valid (B) valid
(C) a contradiction (D) none of the above
Answer: (A)

Q Let P, Q and R be three atomic prepositional assertions. Let X denote (P v Q) → R and Y

denote (P → R) v (Q → R). Which one of the following is a tautology? (GATE-2005) (2 Marks)
(A) X ≡ Y (B) X → Y (C) Y → X (D) ¬ Y → X
Answer: (B)

Q Consider the following propositional statements: (GATE-2006) (2 Marks)

P1 : ((A ∧ B) → C)) ≡ ((A → C) ∧ (B → C))
P2 : ((A ∨ B) → C)) ≡ ((A → C) ∨ (B → C))
Which one of the following is true?
(A) P1 is a tautology, but not P2 (B) P2 is a tautology, but not P1
(C) P1 and P2 are both tautologies (D) Both P1 and P2 are not tautologies
Answer: (D)

Q Let p, q, r and s be four primitive statements. Consider the following arguments:

P:[(¬p∨q)∧(r→s)∧(p∨r)]→(¬s→q) Q:[(¬p∧q)∧[q→(p→r)]]→¬r
R:[[(q∧r)→p]∧(¬q∨p)]→r S:[p∧(p→r)∧(q∨¬r)]→q
Which of the above arguments are valid? (GATE-2004) (2 Marks)
a) P and Q only b) P and R only
c) P and S only d) P, Q, R and S
Answer: (C)
Q Which of the following is/are a tautology? (GATE-1992) (1 Marks)
a) (a ∨ b) → (b ∧ c) b) (a ∧ b) → (b ∨ c)
c) (a ∨ b) → (b → c) d) (a → b) → (b → c)
Answer: (B)

Q If the proposition ¬p → q is true, then the truth value of the proposition ¬p ∨ (p → q),
where ¬ is negation, ∨ is inclusive OR and → is implication, is (GATE-1995) (2 Marks)
a) True b) Multiple Values b) False c) Cannot be determined
Answer: (D)

Q Which of the following is false? Read ∧ as AND, ∨ as OR, ¬ as NOT, → as one-way

implication and ↔ as two-way implication (GATE-1996) (2 Marks)
a) ((x → y) ∧x) →y b) ((¬x→ y) ∧(¬x→¬y)) →x
c) (x→ (x ∨ y)) d) ((x ∨ y) ↔ (¬x→¬y))
Answer: (D)

Q Let a, b, c, d be propositions. Assume that the equivalences a ↔ (b V ¬b) and b ↔ c hold.

Then the truth value of the formula (a ∧ b) → (a ∧ c) ∨ d is always. (GATE-2003) (2 Marks)
(A) True (B) False
(C) Same as the truth value of b (D) Same as the truth value of d
Answer: (A)

Q The following resolution rule is used in logic programming:

Derive clause (P v Q) from clauses (P v R), (Q v ¬ R)
Which of the following statements related to this rule is FALSE? (GATE-2003) (2 Marks)
(A) ((P v R) ^ (Q v ¬ R)) (P v Q) is logically valid
(B) (P v Q) ⇒ ((P v R) ^ (Q v ¬ R)) is logically valid
(C) (P v Q) is satisfiable if and only if (P v R) ^ (Q v ¬ R) is satisfiable
(D) (P v Q) ⇒ FALSE if and only if both P and Q are unsatisfiable
Answer: (B)

Q “If X, then Y unless Z” is represented by which of the following formulae in propositional

logic? (GATE-2002) (1 Marks)
(A) (X ^ ¬ Z) → Y (B) (X ^ Y) → ¬ Z
(C) (X → (Y ^ ¬ Z) (D) (X → Y (^ ¬ Z)
Answer: (A)

Q “If X, then Y unless Z” is represented by which of the following formulae in propositional

logic? (NET-Jan-2017)
A) (X ∧ Y) → ¬ Z B) (X ∧ ¬ Z) → Y
C) X → (Y ∧ ¬ Z) D) Y → (X ∧ ¬ Z)
Ans. B

Q Consider the statement, “Either – 2 ≤ x ≤ – 1 or 1 ≤ x ≤2”. The negation of this statement is

(NET-July-2016)
A) x < – 2 or 2 < x or – 1 < x < 1 B) x < – 2 or 2 < x
C) – 1 < x < 1 D) x ≤ – 2 or 2 < x or – 1 < x < 1
Ans. A

Q The binary operation c is defined as follows

P Q P⊙Q
T T T
T F T
F T F
F F T

Which one of the following is equivalent to P∨Q? (GATE-2009) (2 Marks)

a) (∼Q⊙∼P) b) (P⊙∼Q) c) (∼P⊙Q) d) (∼P⊙∼Q)
Answer: (B)

Q A logical binary relation ⊙, is defined as follows: (GATE-2006) (2 Marks)

A B A⊙B
T T T
T F T
F T F
F F T

Let ∼ be the unary negation (NOT) operator, with higher precedence then ⊙.
Which one of the following is equivalent to A∧B?
a) (∼A⊙B) b) ∼(A⊙∼B) c) ∼(∼A⊙∼B) d) ∼(∼A⊙B)
Answer: (D)

Q Consider a proposition given as: (NET-June-2015)

“x ≥ 6, if x2 ≥ 5 and its proof as: If x ≥ 6, then x2 = x.x ≥ 6.6 = 36 ≥ 25
Which of the following is correct w.r.to the given proposition and its proof?
(a) The proof shows the converse of what is to be proved.
(b) The proof starts by assuming what is to be shown.
(c) The proof is correct and there is nothing wrong.
(A) (a) only (B) (c) only (C) (a) and (b) (D) (b) only
Ans. C

Q find which of the following arguments are valid?

((p ∨ q) ∨ ¬p) = T
¬ (p ∨ q) ∨ (¬p ∧ q) ∨ p = T
((p → q) ←→ (¬q → ¬p)) ∧ r = r
(p ∨ ¬ (p ∧ q)) = T
(p ∧ q) ∧ (¬p ∨ ¬q) = F
(¬p ∧ (¬q ∧ r)) ∨ (q ∧ r) ∨ (p ∧ r) = r
(p ∨ q) ∧ ¬ (¬p ∧ (¬q ∨ ¬r)) ∨ (¬p ∧ ¬q) ∨ (¬p ∧¬ r) = T

p →q
q →r
¬r
¬p

r →s
p →q
r∨p
s∨q

¬p → ¬r
¬S
P→w
R∨s
W

(p → (r → s))
¬r → ¬p
p
s

¬x → y
¬x ∧ ¬y
x

(p → (q → s))
¬r ∨ p
q
p
s
 First order Predicate Logic
Statement involving variables
‘x > 3’
these statements is neither true nor false when the value of the variable is not specified. In
first order predicate logic we will see the ways that proposition can be produced from such
statements.

This statement has two parts first part variable x, which is the subject of the statements.

The second part predicate >3, refers to the property that the subject of the statement can
have.
First-order logic is symbolized reasoning in which each sentence, or statement, is broken
down into a subject and a predicate.

We can denote the statement x is greater than 3 by P(x), where P denotes the predicates.
“>3” and x is the variable. The statement P(x) is also said to be the value of the propositional
function P at x. once a value has been assigned to the variable, the statement p(x) becomes a
proposition and has a truth value.

In general, a statement involving then n variable x1, x2, x3…. xn can be denoted by P (x1, x2,
x3…., xn)

A statement of the form P (x1, x2, x3…., xn) is the value of the propositional function p at the
n-tuple (x1, x2, x3…, xn) and p is also called a predicate.

When all the variables in a propositional function are assigned values, the resulting
statements becomes a proposition with a certain truth value or false value. However, there is
another important way called quantification, to create a proposition from a propositional
function. The area of logic that deals with predicates and quantifiers is called the predicate
calculus.
Universal quantifiers: - the universal quantification of a propositional function is the
proposition that asserts that P(x) is true for all values of x in the universe of discourse. The
universe of discourse specifies the possible value of x.

∀x P(x), i.e. for all value of a P(x) is true

Existential quantifiers: - with existential quantifier of a propositional that is true if and only if
P(x) is true for at least one value of x in the universe of discourse. There exists an element a x
is the universe of discourse such that P(x) is true.

∃x P(x), i.e. for at least one value of a P(x) is true

Negation

¬ [∀x P(x)] = ∃x ¬P(x)

¬ [∃x P(x)] = ∀x ¬P(x)

Propositional function = predicate

In logic and mathematics second-order logic is an extension of first-order logic, which itself is
an extension of propositional logic. Second-order logic is in turn extended by higher-order
logic and type theory.
Universal specification: - is used to conclude P(c) is true, where c is a particular member of
universe of discourse, given the premise ∀x P(x).

i.e. if ∀x P(x) then P(c) is true. Where c is nay element in the universe of discourse.

Universal generalization: - is the rule of inference that states that ∀x P(x) is true given the
premise that P(c) is true for all element c in the universe of discourse. If P(c) is true for any
element c in the universe of discourse then ∀x P(x)

Existential specification: - is the rule that allows us to conclude that there is an element c. in
the universe of discourse for which P(c) is true if we know that ∃x P(x) is true. We cannot
select an arbitrary value of c here but rather it must be a c from which P(c) is true. i.e. if ∃x
P(x) then for an element a in the universe of discourse. P(a)

Existential generalization: - is the rule of inference that is used to conclude that ∃x P(x) is
true when a particular element c with P(c) true is known. i.e. if we know one element c in the
universe of discourse for which P(c) is true, then we know that ∃x P(x) is true.
 GATE Practice question (Quantifier)

Q Negation of the proposition ∃x H(x) (NET-Jan-2017)

(A) ∃x ¬H(x) (B) ∀x ¬H(x) (C) ∀x H(x) (D) ¬x H(x)
Ans. B

Q Consider the following well-formed formulae:

1) ¬∀x(P(x)) 2) ¬∃x(P(x)) 3) ¬∃x(¬P(x)) 4) ∃x(¬P(x))
Which of the above are equivalent? (GATE-2009) (2 Marks)
a) I and III b) I and IV c) II and III d) II and IV
Answer: (B)

Q Which one of the following is NOT logically equivalent to ¬∃x(∀y(α) ∧ ∀z(β))? (GATE-2013)
(2 Marks)
a) ∀x(∃z(¬β) → ∀y(α)) b) ∀x(∀z(β) → ∃y(¬α))
c) ∀x(∀y(α) → ∃z(¬β)) d) ∀x(∃y(¬α) → ∃z(¬β))
Answer: (A & D)

Q Let a(x, y), b(x, y,) and c(x, y) be three statements with variables x and y chosen from some
universe. Consider the following statement: (GATE-2004) (2 Marks)
(∃x)(∀y) [(a(x, y) ∧ b(x, y)) ∧ ¬c(x, y)]
Which one of the following is its equivalent?
a) (∀x)(∃y) [(a(x, y) ∨ b(x, y)) → c(x, y)] b) (∃x)(∀y)[(a(x, y) ∨ b(x, y)) ∧ ¬c(x, y)]
c) ¬(∀x)(∃y)[(a(x, y) ∧ b(x, y)) → c(x, y)] d) ¬(∀x)(∃y)[(a(x, y) ∨ b(x, y))→c(x, y)]
Answer: (C)

Q Which one of the following well-formed formulae is a tautology? (GATE-2015) (2 Marks)

a) ∀x∃y R(x, y) ↔ ∃y∀x R(x, y)
b) (∀x[∃y R(x, y) → S(x, y)]) → ∀x∃y S(x, y)
c) [∀x∃y(P(x, y) → R(x, y))] ↔ [∀x∃y(¬P(x, y) ∨ R(x, y))]
d) ∀x∀y P(x, y) → ∀x∀y P(y, x)
Answer: (c)

Q Which one of the following well-formed formulae in predicate calculus is NOT valid?
a) (∀x p(x) ⟹ ∀x q(x)) ⟹ (∃x ¬p(x) ∨ ∀x q(x))
b) (∃x p(x) ∨ ∃x q(x)) ⟹ ∃x(p(x) ∨ q(x))
c) ∃x(p(x) ∧ q(x)) ⟹ (∃x p(x) ∧ ∃x q(x))
d) ∀x(p(x) ∨ q(x)) ⟹ (∀x p(x) ∨ ∀x q(x)) (GATE-2016) (2 Marks)
Answer: (D)
Q Which of the following predicate calculus statements is/are valid? (GATE-1992) (1 Marks)
a) (∀(x))P(x) ∨ (∀(x))Q(x) ⟹ (∀(x))(P(x)∨Q(x))
b) (∃(x))P(x) ∧ (∃(x))Q(x) ⟹ (∃(x))(P(x) ∧ Q(x))
c) (∀(x))(P(x) ∨ Q(x)) ⟹ (∀(x))P(x) ∨ (∀(x))Q(x)
d) (∃(x))(P(x) ∨ Q(x))⟹∼(∀(x))P(x) ∨ (∃(x))Q(x)
Answer: (A)

Q Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always
TRUE? (GATE-2005) (2 Marks)
(A) ((∀x(P(x) ∨ Q(x)))) ⟹ ((∀xP(x)) ∨ (∀xQ(x)))
(B) (∀x(P(x) ⟹ Q(x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x)))
(C) (∀x(P(x)) ⟹ ∀x(Q(x))) ⟹ (∀x(P(x) ⟹ Q(x)))
(D) (∀x(P(x)) ⇔ (∀x(Q(x)))) ⟹ (∀x(P(x) ⇔ Q(x)))
Answer: (B)

Q Which one of these first-order logic formulae is valid? (GATE-2007) (2 Marks)

(A) ∀x(P(x) => Q(x)) => (∀xP(x) => ∀xQ(x))
(B) ∃x(P(x) ∨ Q(x)) => (∃xP(x) => ∃xQ(x))
(C) ∃x(P(x) ∧ Q(x)) (∃xP(x) ∧ ∃xQ(x))
(D) ∀x∃y P(x, y) => ∃y∀x P(x, y)
Answer: (A)

Q Which of the following is a valid first order formula? (Here α and β are first order formulae
with x as their only free variable) (GATE-2003) (2 Marks)
a) {(∀x)[α] ⇒ (∀x)[β]} ⇒ {(∀x)[α ⇒ β]}
b) (∀x)[α]⇒(∃x)[α∧β]
b) {(∀x)[α ∨ β]} ⇒ {(∃x)[α]) ⇒ (∀x)[α]}
c) (∀x)[α ⇒ β] ⇒ (((∀x)[α]) ⇒ (∀x)[β])
Answer: (D)

Q Consider the first-order logic sentence

F: ∀x (∃y R (x, y)). Assuming non-empty logical domains, which of the sentences below are
implied by F? (GATE-2017) (1 Marks)
I. ∃y (∃x R (x, y)) II. ∃y (∀x R (x, y)) III. ∀y (∃x R (x, y)) IV. ∼∃x (∀y ∼R (x, y))
(A) IV only (B) I and IV only (C) II only (D) II and III only
Answer: (B)

Q Let P(m, n) be the statement “m divides n” where the universe of discourse for both the
variables is the set of positive integers. Determine the truth values of each of the following
propositions: (NET-Dec-2013)
I. ∀m ∀n P(m, n), II. ∃m ∀n P(m, n)
(A) Both I and II are true (B) Both I and II are false
(C) I – false & II – true (D) I – true & II – false
ANS: C

Q Let Q (x, y) denote “x + y = 0” and let there be two quantifications given as

(i) ∃y∀xQ(x, y)
(ii) ∀x∃yQ(x, y)
Where, x and y are real numbers. Then which of the following is valid? (NET-Dec-2012)
(a) I is true and II is false (b) I is false and II is true
(c) I is false and II is also false (d) both I and II are true
ANS: B

Q Let P(m, n) be the statement “m divides n” where the Universe of discourse for both the
variables is the set of positive integers. Determine the truth values of the following
propositions. (NET-Dec-2015)
(a)∃m ∀n P(m, n) (b)∀n P(1, n) (c) ∀m ∀n P(m, n)
Codes:
A) (a) - True; (b) - True; (c) – False B) (a) - True; (b) - False; (c) – False
C) (a) - False; (b) - False; (c) – False D) (a) - True; (b) - True; (c) – True
Ans. A

Q What is the logical translation of the following

lowing statement? (GATE-2013) (2 Marks)
"None of my friends are perfect."
A) ∃x(F(x) ∧ ¬P(x)) B) ∃x(¬F(x) ∧ P(x))
C) ∃x(¬F(x) ∧ ¬P(x)) D) ¬∃x(F(x) ∧ P(x))
Answer: (D)

Q Consider the statement

"Not all that glitters is gold”
Predicate glitters(x) is true if x glitters and predicate gold(x) is true if x is gold. Which one of
the following logical formulae represents the above statement? (GATE-2014) (1 Marks)
a) ∀x: glitters(x) ⇒ ¬gold(x)
b) ∀x: gold(x) ⇒ glitters(x)
c) ∃x: gold(x) ∧ ¬glitters(x)
d) ∃x: glitters(x) ∧ ¬gold(x)
Answer: (D)

Q The CORRECT formula for the sentence, “not all rainy days are cold” is (GATE-2014) (2
Marks)
a) ∀d (Rainy(d) ∧ ~Cold(d)) b) ∀d (~Rainy(d) → Cold(d))
c) ∃d (~Rainy(d) → Cold(d)) d) ∃d (Rainy(d) ∧ ~Cold(d)
Answer: (D)

Q Let Graph(x) be a predicate which denotes that x is a graph. Let Connected(x)be a

predicate which denotes that x is connected. Which of the following first order logic
sentences DOES NOT represent the statement: “Not every graph is connected”? (GATE-2007)
(2 Marks)
(A) ¬∀x (Graph(x) → Connected(x)) (B) ∃x (Graph(x) ∧ ¬Connected(x))
(C) ¬∀x (¬Graph(x) ∨ Connected(x)) (D) ∀x (Graph(x) → ¬Connected(x))
Answer: (D)

Q 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 is precious (GATE-2009) (2 Marks)
(A) ∀x (P(x) → (G(x) ∧ S(x))) (B) ∀x ((G(x) ∧ S(x)) → P(x))
(C) ∃x ((G(x) ∧ S(x)) → P(x) (D) ∀x ((G(x) ∨ S(x)) → P(x))
Answer: (D)

Q 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 ∀x∃y ∃t (¬F (x, y, t))? (GATE-2010) (2 Marks)
(A) Everyone can fool some person at some time
(B) No one can fool everyone all the time
(C) Everyone cannot fool some person all the time
(D) No one can fool some person at some time
Answer: (B)

Q What is the correct translation of the following statement into mathematical logic?

“Some real numbers are rational” (GATE-2012) (1 Marks)

a) ∃x (real(x) ∨ rational(x)) b) ∀x (real(x) → rational(x))

c) ∃x (real(x) ∧ rational(x)) d) ∃x (rational(x) → real(x))
Answer: (C)

Q What is the first order predicate calculus statement equivalent to the following?

Every teacher is liked by some student (GATE-2005) (2 Marks)

(A) ∀(x) [teacher (x) → ∃(y)[student (y) → likes (y, x)]]
(B) ∀(x) [teacher (x) → ∃(y)[student (y) ^ likes (y, x)]]
(C) ∃(y) ∀(x) [teacher (x) → [student (y) ^ likes (y, x)]]
(D) ∀(x) [teacher (x) ^ ∃(y)[student (y) → likes (y, x)]]
Answer: (B)

Q Identify the correct translation into logical notation of the following assertion.

Some boys in the class are taller than all the girls

Note: taller (x, y) is true if x is taller than y. (GATE-2004) (1 Marks)

(A) ( ∃x) (boy(x) → ( ∃y) (girl(y) ^ taller (x, y)))
(B) ( ∃x) (boy(x) ^ ( ∀y) (girl(y) ^ taller (x, y)))
(C) ( ∃x) (boy(x) → ( ∀y) (girl(y) → taller (x, y)))
(D) ( ∃x) (boy(x) → (∀y) (girl(y) ^ taller (x, y)))
Answer: (D)

Q Let fsa and pda be two predicates such that fsa(x) means x is a finite state automaton, and
pda(y) means that y is a pushdown automaton. Let equivalent be another predicate such that
equivalent (a, b) means a and b are equivalent. Which of the following first order logic
statements represents the following. Each finite state automaton has an equivalent
pushdown automaton. (GATE-2008) (1 Marks)
a) (∀x fsa(x)) ⟹ (∃y pda(y) ∧ equivalent(x, y))
b) ¬∀y(∃x fsa(x) ⟹ pda(y) ∧ equivalent(x, y))
c) ∀x∃y (fsa(x) ∧ pda(y) ∧ equivalent(x, y))
d) ∀x∃y(fsa(y) ∧ pda(x) ∧ equivalent(x, y))
Answer: (A)

Q Which one of the first order predicate calculus statements given below correctly express
the following English statement? (GATE-2006) (2 Marks)

“Tigers and lions attack if they are hungry or threatened”

a) ∀x[(tiger(x) ∧ lion(x)) → (hungry(x) ∨ threatened(x)) → attacks(x)]

b) ∀x[(tiger(x) ∨ lion(x)) → (hungry(x) ∨ threatened(x)) ∧ attacks(x)]
c) ∀x[(tiger(x) ∨ lion(x)) → attacks(x) → (hungry(x) ∨ threatened(x))]
d) ∀x[(tiger(x) ∨ lion(x)) → (hungry(x) ∨ threatened(x)) → attacks(x)]

Q The truth value of the statements : ∃!xP(x) → ∃xP(x) and ∃!x~ P(x) → ~∀xP(x), (where the
notation ∃!xP(x) denotes the proposition “There exists a unique x such that P(x) is true”) are :
(NET-Dec-2013)
(A) True and False (B) False and True
(C) False and False (D) True and True
Q The notation ∃!xP(x) denotes the proposition “there exists a unique x such that P(x) is
true”. Give the truth values of the following statements: (NET-June-2014)
I. ∃!xP(x) → ∃xP(x) II. ∃!x ¬ P(x) → ¬∀xP(x)
(A) Both I & II are true. (B) Both I & II are false.
(C) I – false, II – true (D) I – true, II – false

Q Which one of the following options is CORRECT given three positive integers x, y and z, and
a predicate? (GATE-2011) (2 Marks)
P(x) = ¬(x=1) ∧∀y(∃z(x=y*z) ⇒(y=x) ∨(y=1))
(A) P(x) being true means that x is a prime number
(B) P(x) being true means that x is a number other than 1
(C) P(x) is always true irrespective of the value of x
(D) P(x) being true means that x has exactly two factors other than 1 and x
Answer: (A)
 Group Theory
• Group theory is very important mathematical tool which is used in a number of areas
in research and application. Using group theory, we can estimate the strength of a
set with respect to an operator.
• This idea will further help us in research field to identify the correct mathematical
system to work in a particular research area. E.g. can we use natural in complex
problem area like soft computing or studying black holes.
• now we will directly study some of the basic set related properties and will define
some structure based on the properties and will check those properties on basics
number systems like natural numbers, integers, real numbers etc.
Closure property: - consider a non-empty set A and a binary operation * on A. A is said to
be closed with respect to *, if ∀ a, b ∈ A, then a*b ∈ A.
Algebraic Structure: - A non-empty set A is said to be an algebraic structure with respect to
a binary operation *, if A satisfy closure property with respect to *.
Associative property: - Consider a non-empty set A and a binary operation * on A. A is said
to be associative with respect to *, if ∀ a, b, c ∈ A, then (a*b) *c = a*(b*c)
Semi-Group: - A non-empty set A is said to be a Semi-group with respect to a binary
operation *, if A satisfy closure, Associative property with respect to *.
Identity property: - Consider a non-empty set A and a binary operation * on A. A is said to
satisfy identity property with respect to *, if ∀ a ∈ A, there must be unique e ∈ A, such that
a*e = e*a = a
• If there exist an identity element in a set with respect to *, it will be exactly one.
Monoid: - A non-empty set A is said to be a Monoid with respect to a binary operation *, if
A satisfy closure, Associative, identity property with respect to *.
Inverse property: - Consider a non-empty set A and a binary operation * on A. A is said to
satisfy inverse property with respect to *, if ∀ a ∈ A, there must be unique element a-1 ∈ A,
such that
a* a-1 = a-1*a = e
• Every element has a unique inverse, and no two elements will have the same inverse
• Identity element is its own inverse.
Group: - A non-empty set A is said to be a group with respect to a binary operation *, if A
satisfy closure, Associative, identity, inverse property with respect to *.
• Identity element is always the inverse of itself
• If the total number of elements in a group is even then there exists at least one
element in the group who is the inverse of itself
• Some time it is also possible that every element is inverse of itself in a group
• In a group (a * b)-1 = b-1 * a-1 for ∀ a, b ∈ A
• Cancelation law holds good
a*b=a*c → b=c
a*c=b*c → a=b
Commutative property: - Consider a non-empty set A and a binary operation * on A. A is
said to satisfy commutative property with respect to *, if ∀ a, b ∈ A, such that
a* b = b*a
Abelian Group: - A non-empty set A is said to be a group with respect to a binary operation
*, if A satisfy closure, Associative, identity, inverse, commutative property with respect to *.

Q Some group (G,o) is known to be abelian. Then, which one of the following is true for G?
(GATE-1994) (2 Marks)
A) g = g−1 for every g ∈G B) g=g2 for every g ∈ G
B) (goh)2=g2oh2 for every g, h ∈ G D) G is of finite order
Answer: (c)

Q Which of the following properties a Group G must hold, in order to be an Abelian group?
(a)The distributive property
(b)The commutative property
(c)The symmetric property
a) (a) and (b) b) (b) and (c)
c) (a) and (b) d) (a), (b) and (c)
Ans. D

Q Consider the set H of all 3 × 3 matrices of the type

𝑎 𝑓 𝑒
0 𝑏 𝑑
0 0 𝑐
where a, b, c, d, e and f are real numbers and abc ≠ 0. Under the matrix multiplication
operation, the set H is (GATE-2005) (2 Marks)
(A) a group (B) a monoid but not a group
(C) a semigroup but not a monoid (D) neither a group nor a semigroup
Answer: (A)

Q Let A be the set of all non-singular matrices over real number and let ∗ be the matrix
multiplication operation. Then (GATE-1994) (2 Marks)
a) A is closed under ∗ but ⟨A,∗⟩ is not a semigroup.
b) ⟨A,∗⟩ is a semigroup but not a monoid.
c) ⟨A,∗⟩ is a monoid but not a group.
d) ⟨A,∗⟩ is a a group but not an abelian group.
Answer: (d)
Q Which of the following statements is FALSE? (GATE-1996) (1 Marks)
a) The set of rational numbers is an abelian group under addition
b) The set of integers in an abelian group under addition
c) The set of rational numbers form an abelian group under multiplication
d) The set of real numbers excluding zero is an abelian group under multiplication
Answer: (c)
 Algebraic Semi-Group Monoid Group Abelian
Structure Group
(N, +) YES YES NO NO NO
(N, -) NO NO NO NO NO
(N, /) NO NO NO NO NO
(N, *) YES YES YES NO NO
(Z, +) YES YES YES YES YES
(Z, -) YES NO NO NO NO
(Z, /) NO NO NO NO NO
(Z, *) YES YES YES NO NO
(R, +) YES YES YES YES YES
(R, -) YES NO NO NO NO
(R, /) NO NO NO NO NO
(R, *) YES YES YES NO NO
(M, +) YES YES YES YES YES
(M, *) YES YES YES NO NO
(E, +) YES YES YES YES YES
(E, *) YES YES NO NO NO
(O, +) NO NO NO NO NO
(O, *) YES YES YES NO NO
(Z*, /) YES YES YES YES NO
(R*, /) YES YES YES YES YES
(M*, *) YES YES YES YES NO

Q Which one of the following in NOT necessarily a property of a Group? (GATE-2009) (2

Marks)
(A) Commutativity (B) Associativity
(C) Existence of inverse for every element (D) Existence of identity
Answer: (A)

Q let A = {1, 3, 5, ……., ∞} and B = {2, 4, 6, ……., ∞}, what is the highest structure achieved
by each of them?
1) (A,+) 2) (A,*) 3) (B,+) 4) (B,*)

Q Consider a set of natural numbers N, with respect to *, such that a * b = ab which of the
following is true?
a) semi group but not monoid b) A monoid but not a group
c) A group d) not a semi group
Ans: d

Q The binary operator ≠ is defined by the following truth table (GATE-2015) (1 Marks)
p q P! = q
0 0 0
0 1 1
1 0 1
1 1 0
Which one of the following is true about the binary operator ≠?
(A) Both commutative and associative (B) Commutative but not associative
(C) Not commutative but associative (D) Neither commutative nor associative
Answer: (A)

Q Which of the following is true? (GATE-2002) (2 Marks)

(A) The set of all rational negative numbers forms a group under multiplication.
(B) The set of all non-singular matrices forms a group under multiplication.
(C) The set of all matrices forms a group under multiplication.
(D) Both (2) and (3) are true.
Answer: (B)

Q A binary operation α on a set of integers is defined as x α y = x2 + y2. Which one of the

following statements is TRUE about α? (GATE-2013) (1 Marks)
(A) Commutative but not associative (B) Both commutative and associative
(C) Associative but not commutative (D) Neither commutative nor associative
Answer: (A)

Q let {p, q, r, s} be the set. A binary operation * is defined on the set and is given by the
following table:

* p q r s
P p r s p
q p q r s
r p q p r
S p q q q

Which of the following is true about the binary operation?

a) it is commutative but not associative
b) it is associative but not commutative
c) it is both associative and commutative
d) it is neither associative nor commutative
Ans: d

Q Consider a set of integers Z, with respect to *, such that a * b = max (a, b) which of the
following is true?
a) Algebraic structure b) semi-group
c) Monoid d) group
Ans: b

Q Consider a set of integers Z, with respect to *, such that a * b = min (a, b) which of the
following is true?
a) Algebraic structure b) semi-group
c) Monoid d) group
Ans: b

Q which of the following is not a group?

a) {……. -6, -4, -2, 0, 2, 4, 6, ……}, + b) {…. -3k, -2k, -k, 0, k, 2k, 3k, ….}, + [k ∈ Z]
c) {2n, n ∈ N}, * d) set of complex number, *
Ans: d

Q Consider the set of all integers(Z) with the operation defined as

m * n = m + n + 2, m, n ∈ Z
if (z, *) forms a group, then determine the left identity element
a) 0 b) -1 c) -2 d) 2
Ans: c

Q Consider a set of positive rational number with respect to an operation *, such that a*b =
(a.b)/3, it is known that the it is an abelian group, which of the following is not true?
a) identity element e = 3 b) inverse of a = 9/a
c) inverse of 2/3 = 6 d) inverse of 3 = 3
Ans: c

Q Consider the set ∑* of all strings over the alphabet ∑ = {0, 1}. ∑* with the concatenation
operator for strings (GATE-2003) (1 Marks)
(A) does not form a group
(B) forms a non-commutative group
(C) does not have a right identity element
(D) forms a group if the empty string is removed from ∑*
Answer: (A)

Q Consider the set {a, b, c} with binary operators + and × defined as follows:
+ a b c × a b c

a b a c a a b c

b a b c b b c a

c a c b c c c b

For example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following set of equations:

(a × x) + (a × y) = c
(b × x) + (c × y) = c
The number of solution(s) (i.e., pair(s) (x, y)) that satisfy the equations is : (GATE-2003) (2
Marks)
(A) 0 (B) 1 (C) 2 (D) 3
Answer: (C)
Finite Group: - A group with finite number of elements is called a finite group
Order of group: - order of a group is denoted by O(G) = no of elements in G
• Group with a single element must be an identity element

Q Check out which of the following is a finite group?

• {0}, +
• {0}, *
• {1}, +
• {1}, *
• {0,1}, +
• {0,1}, *
• {-1, 0, 1}, +
• {-1, 0, 1}, *
• {-1, 1}, +
• {-1, 1}, *
• {-2, -1, 0, 1, 2}, +
• {-2, -1, 0, 1, 2}, *
• {1, w, w2}, *
• {-1, 1, I, -i}, *
Addition modulo: - addition modulo is a binary operator denoted by +m such that
a +m b = a + b if (a + b < m)
a +m b = a + b - m if (a + b >= m)
Multiplication modulo: - Multiplication modulo is a binary operator denoted by *m such
that
a *m b = a * b if (a * b < m)
a *m b = (a * b) % m if (a * b >= m)
Q Check out which of the following is a group?
• {0,1,2,3}, +4
• {0,1,2,3}, *4
• {1,2,3}, +4
• {1,2,3}, *4
• {0,1,2,3,4}, +5
• {0,1,2,3,4}, *5
 • {1,2,3,4}, +5
• {1,2,3,4}, *5
• {0,1,2,3,4,5,6}, +7
• {0,1,2,3,4,5,6}, *7
• {1,2,3,4,5,6}, +7
• {1,2,3,4,5,6}, *7
• {1,3,5,7}, *8
• {1,2,4,7,8,11,13,14}, *15
• {1,2,3, 4……., p-1}, *p
• {0,1,2,3, 4……., p-1}, *p
• {1,2,3, 4……., p-1}, +p
• {0,1,2,3, 4……., p-1}, +p

Q {0,1,2,3,4,5}, +6 is a group which of the following is not true?

a) 1-1 = 5 b) 2-1 = 4 c) 3-1 = 6 d) 0-1 = 0
ans: c

Q {1,2,3,4,5,6}, *7 is a group which of the following is not true?

a) 1-1 = 1 b) 2-1 = 4 c) 3-1 = 5 d) 6-1 = 6
Ans: d

Q {1,3,5,7}, *8 is a group which of the following is not true?

a) 1-1 = 1 b) 3-1 = 3 c) 5-1 = 5 d) 7-1 = 7
Ans: all are true

Q {1,2,4,7,8,11,13,14}, *15 is a group which of the following is not true?

a) 2-1 = 8 b) 4-1 = 4 c) 7-1 = 13 d) 11-1 = 14
Ans: d
Q The set {1, 2, 3, 5, 7, 8, 9} under multiplication modulo 10 is not a group. Given below are
four plausible reasons. Which one of them is false? (GATE-2006) (1 Marks)
(A) It is not closed (B) 2 does not have an inverse
(C) 3 does not have an inverse (D) 8 does not have an inverse
Answer: (C)
Q The set {1, 2, 4, 7, 8, 11, 13, 14} is a group under multiplication modulo 15. The inverses
of 4 and 7 are respectively (GATE-2005) (2 Marks)
(A) 3 and 13 (B) 2 and 11 (C) 4 and 13 (D) 8 and 14
Answer: (C)

Q The following is the incomplete operation table a 4-element group. (GATE-2004) (2

Marks)

* ea bc
E ea bc
Aabc e
B
C

The last row of the table is

(A) c a e b (B) c b a e (C) c b e a (D) c e a b
Answer: (D)

Q Consider the binary operation ⨁ over set Zn = {0, 1, 2, …..., n-1}

a⨁b=a+b if (a + b < n)
a⨁b=a+b-m if (a + b >= n)
a) it is closed b) it does not form a group
c) it forms a group but not an abelian group d) it is an abelian group
Ans: d
 Sub Group
• The subset of a group may or may not be a group
• When the subset of a group is also a group then it is called sub group
• Union of two subgroup may or may not be a subgroup
• Intersection of two subgroup is always a subgroup
• Lagrange’s theorem - the order of a group is always exactly divisible by the order
of a sub group
• the identity element of a group and its sub group is always same

Q consider a group G = {1,3,5, 7}, *8 which of the following sub set of this set does not form
is sub group?
a) {0,1} b) {1,3} c) {1,5} d) {1,7}
Ans: a

Q G = {1,3,5,7}, *8
then G = {1,3}, *8 G = {1,5}, *8

Q Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L != G and

that the size of L is at least 4. The size of L is __________. (GATE-2014) (1 Marks)
(A) 3 (B) 5 (C) 7 (D) 9
Answer: (B)

Q let (A, *) be a group of prime order, how many proper-subgroups are possible for A?
a) 0 b) 1 c) P-1 d) P

Q Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of
G is _______ . (GATE-2014) (1 Marks)
Answer: (42)
Order of an element: - (A, *) be a group, then ∀ a ∈ A, order of a is denoted by O(a)
O(a) = smallest positive Let integer n, such that an = e
• order of identity element is always one
• order of an element and its inverse is always same
• order of an element in an infinite group does not exist or infinite expect identity

Generating element or Generator: - A element ‘a’ is said to be a generating element, if

every element of A is an integral power of a, i.e. every element of A can be represented
using power of a.
A = {a1, a2, a3, a4, a5….}

Cyclic group: - A group (A, *) is said to be a cyclic group if it contains at least one generator.
• In a cyclic group if an element is a generator than its inverse will also be a generator
• The order of a cyclic group is always the order of the generating element of G
Q consider a set on cube root of unity {1, w, w2}, * and find the order of each element?
Q consider a set on forth root of unity {-1, 1, I, -i}, * and find the order of each element?
Q consider a group {0,1,2,3}, +4 and find the order of each element?
Q consider a group {1,3,5,7}, *8 and find the order of each element {1, w, w2}, *
Q consider a group {1,2,4,7,8,11,13,14}, *15 and find the order of each element?

Q For the composition table of a cyclic group shown below

* a b c d
a a b c d
b b a d c
c c d b A
d d c a b

Which one of the following choices is correct? (GATE-2009) (2 Marks)

(A) a, b are generators (B) b, c are generators
(C) c, d are generators (D) d, a are generators
Answer: (C)

Number of generators
Lagrange’s theorem: - let A be a cyclic group of order n, number of Generator in A is
denoted by ɸ(n) = {n(p1-1) (p2-1) (p3-1) ………. (pk-1)} / (p1p2p3………pk)

Q let G be a cyclic group, O(G) = 8, number of generators in G =?

Q let G be a cyclic group, O(G) = 12, number of generators in G =?
Q let G be a cyclic group, O(G) = 70, number of generators in G =?
Q let G be a cyclic group, O(G) = 23100, number of generators in G =?

Q prove the following statement?

a) In a group (G, *) if a*a = a, then proof that a = e, where e is identity element of a.
a*a = a
a*a = a*e
a=e

b) In a group if x’ = x for ∀ a ∈ G in G, then G is an abelian group.

(a*b)-1 = b-1 * a-1
a*b = b*a
as we know according to question a = a-1 and b = b-1
(a*b)-1 = b-1 * a-1

c) In a group (G, *) , if (a*b)2 = a2 * b2 , then prove that G is an abelian group

(a*b) * (a*b) = (a*a) * (b*b)
After applying both left and right cancelation we get
(a*b) = (b*a)

Q (D12, *) where a*b = g.c.d of (a, b) ∀a, b∈ D12 then (D12, *) is

a) a semigroup but not monoid b) a monoid but not a group
c) a group d) not a semi group
And: b

Q Let s = set of all integers. A binary operation * is defined by

a*b=a+b+3
consider the following statements
S1: (S,*) is a group
S2: -3 is identity element of (S, *)
S3: the inverse of -6 is 0
which of the following are true
a) Only S1 and S2 b) Only S2 and S3
c) Only S1 and S3 d) Only S1 ,S2 and S3
Ans: d

Q There are two elements x, y in a group (G, ∗) such that every element in the group can be
written as a product of some number of x’s and y’s in some order. It is known that
x ∗ x = y ∗ y = x ∗ y ∗ x ∗ y = y ∗ x ∗ y ∗ x = e where e is the identity element. The maximum
number of elements in such a group is __________. (GATE-2014) (2 Marks)
Answer: 4
x * x = e, x is its own inverse
y * y = e, y is its own inverse
(x*y) * (x* y) = e, x*y is its own inverse
(y*x) * (y*x) = e, y*x is its own inverse
also x*x*e = e*e can be rewritten as follows
x*y*y*x = e*y*y*e = e, (Since y *y = e)
(x*y) * (y*x) = e shows that (x *y) and (y *x)
are each other’s inverse and we already know that
(x*y) and (y*x) are inverse of its own.
As per (G,*) to be group any element should have
only one inverse element (unique)
This implies x*y = y*x (is one element)
So the elements of such group are 4 which are
{x, y, e, x*y}.
 Graph Theory
• A graph G (V, E) consist of a set off objects V = {V1, V2, V3….,VN} called vertices and
another set E = {E1, E2, E3,….,En} whose elements are called edges.
• Each edge ek is identified with an unordered pair (vi, vj) of vertices.
• The vertices vi, vj associated with edge ek are called the end vertices of ek.
• Self-Loop: Edge having the same vertex (vi, vi) as both its end vertices is called self-loop.
• Parallel Edge: When more than one edge associated with a given pair of vertices such
edges are referred as parallel edges.
• Adjacent Vertices: If two vertices are joined by the same edges, they are called adjacent
vertices.
• Adjacent Vertices: If two edges are incident on some vertex, they are called adjacent
edges.

Self-Loop Parallel Edge

Simple Graph No No
Multi Graph No Yes
Pseudo Graph Yes No
Graph Yes Yes

• Multi-Graph: A graph G with parallel Edges but no loops is called a Multi-Graph.

• Pseudo Graph: A graph G with self-loop but no parallel edges is called pseudo-Graph.
• Here will be studying undirected and non-weighted simple graph.
 Finite Graph
• Finite graph: - A graph with finite number of vertices as well as the finite number of
edges is called a finite graph.
• For simple graph we can say if the number of vertices are finite then number of edges
will also be finite.
• Null Graph: A graph is said to be null if edge set is empty E = {}, that is a graph with only
vertices but no edges.

• Trivial Graph: A graph with only one vertex without an edge is called trivial graph. It is
the smallest possible.

• Complete or Full Graph or universal graph: In a simple graph there exist an edge
between each and every pair of vertices i.e. every vertex are adjacent to each other,
then the graph is said to be a complete graph, denoted by Kn.
o A simple graph with maximum number of edges are called Complete Graph.
o Number of edges in a simple graph is n(n-1)/2
Q The number of edges in a complete graph with N vertices is equal to: (NET-DEC-2006) (NET-
DEC-2007)
a) N (N - 1) b) [N(N-1)]/2 c) N2 d) 2N-1
Answer: (A)

Q The number of edges in a complete graph of n vertices is (NET-DEC-2009)

(A) n (B) n(n – 1)/2 (C) n(n + 1)/2 (D) n2/2

Q The complete graph with four vertices has k edges where k is: (NET-JUNE-2009)
a) 3 b) 4 c) 5 d) 6
Answer: (d)

Q Maximum number of edges in a n node undirected graph without self-loops is (GATE-2002)

(1 Marks) (NET-DEC-2011)
(A) n2 (B) n(n – 1)/2 (C) n – 1 (D) (n + 1) (n)/2
Answer: (B)

Q Number of simple graph possible with n vertices?

Q Number of simple graph possible with n vertices and e edges?

Q The number of distinct simple graphs with up to three nodes is (GATE-1994) (1 Marks)
a) 15 b) 10 c) 7 d) 9
Answer: (C)

Q How many undirected graphs (not necessarily connected) can be constructed out of a given
set V = {v1, v2, … vn} of n vertices? (GATE-2001) (2 Marks)
(A) n(n-1)/2 (B) 2n (C) n! (D) 2n(n-1)/2
Answer: (D)

Q A simple Graph with ‘n’ vertices and ‘k’ components can have at most (n - k) (n – k + 1)/2
edges?
Ans: The maximum number of edges is clearly achieved when all the components are
complete. Moreover, the maximum number of edges is achieved when all of the components
except one have one vertex.
so if there are k components one component will have n – (k - 1) vertices all the other
components k -1 will have one vertex. So, if a graph has n vertex can have maximum n(n-1)/2
edges, then graph with n – (k - 1) edges will have maximum (n - k) (n – k + 1)/2 edge.

Q 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 (GATE-2012) (2 Marks)
(A) 15 (B) 30 (C) 90 (D) 360
Answer: (C)

Q The maximum number of edges in a bipartite graph on 12 vertices is

__________________________. (GATE-2014) (1 Marks)
Answer: (36)

Q Consider an undirected graph G where self-loops 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 |a − c| <= 1 and |b −
d| <= 1. (GATE-2014) (2 Marks) (NET-AUG-2016)
The number of edges in this graph is __________.
Answer: (506)

Q Consider an undirected random graph of eight vertices. The probability that there is an edge
between a pair of vertices is 1/2. What is the expected number of unordered cycles of length
three? (GATE-2013) (1 Marks)
(A) 1/8 (B) 1 (C) 7 (D) 8
Answer: (C)

Q How many graphs on n labeled vertices exist which have at least (n2 – 3n)/2 edges? (GATE-
2004) (2 Marks)
((n^2) – 3n)/2
a) ((n2 - n)/2)C((n2) – 3n)/2 b)∑𝐾=0 ((n2 - n)/2)CK
c) ((n2) - n)/2)Cn d) ∑n𝐾=0 ((n2 - n)/2)CK
Answer: (D)

Q The 2n vertices of a graph G corresponds to all subsets of a set of size n, for n >= 6. Two
vertices of G are adjacent if and only if the corresponding sets intersect in exactly two
elements. The number of vertices of degree zero in G is (GATE-2006) (2 Marks)
(A) 1 (B) n (C) n+1 (D) 2n
Answer: (C)
Explanation: There are n nodes which are single and 1 node which belong to empty set. And
since they are not having 2 or more elements so they won’t be connected to anyone hence
total number of nodes with degree 0 are n+1 hence answer should be none.
 Degree of a Vertex
• Degree of a Vertex: The degree of a vertex in an undirected graph is the number of
edges associated with it, denoted by deg(vi).
• Isolated vertex: A vertex with degree zero is called isolated vertex.
• Pendant vertex: A vertex with degree one is called pendant vertex.
• Hand-shaking theorem: - Since each edge contribute two degree in the graph, the sum
of the degree of all vertices in G is twice the number of edges in g. ∑𝑛𝑖=1 𝑑(𝑣𝑖) = 2|E|
• The number of vertices of odd degree in a graph is always even. ∑𝑛𝑖=1 𝑑(𝑣𝑖) =
∑𝑒𝑣𝑒𝑛 𝑑(𝑣𝑖) + ∑𝑜𝑑𝑑 𝑑(𝑣𝑖)
• δ(G) * |V(G)| <= 2|E| <= Δ(G)*|V(G)|, where δ(G) is the minimum possible degree of
any vertex in a graph, where Δ(G) is the maximum possible degree of any vertex in a
graph.
• Regular graph: - A graph in which all the vertices are of equal degree is called a regular
graph. E.g. 2-regular graph, 3-regular graph.

Q Which of the following statements is/are TRUE for undirected graphs? (GATE-2013) (1
Marks)
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
a) P only b) Q only
c) Both P and Q d) Neither P nor Q
Answer: (C)

Q Which one of the following is TRUE for any simple connected undirected graph with more
than 2 vertices?(GATE-2009) (1 Marks)
(A) No two vertices have the same degree.
(B) At least two vertices have the same degree.
(C) At least three vertices have the same degree.
(D) All vertices have the same degree.
Answer: (B)
Q A simple graph G contains 21 edges, 3 vertices pf degree 4 and all the remaining vertices are
of degree 2. Then number of vertices |v| is?

Q A simple non-directed graph G has 24 edges and degree of each vertex is 4, then find the
|v|?

Q Consider a simple graph with 35 edges such that 4 vertex of degree 5, 5 vertex of degree 4, 4
vertex of degree 3, find the number of vertices with degree 2?

Q What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices
of degree 2, 3 vertices of degree 4 and remaining of degree 3? (GATE-2004) (2 Marks)
(A) 10 (B) 11 (C) 18 (D) 19
Answer: (D)

Q simple non-directed graph G has 24 edges and degree of each vertex is K, the which of the
following is possible no of vertices?
a) 20 b) 15 c) 10 d) 8

Q G is undirected graph with n vertices and 25 edges such that each vertex has degree at least
3. Then the maximum possible value of n is ________ (GATE-2017) (2 Marks)
Answer: (16)

Q Maximum no of vertex in a simple graph with 35 edges and degree of each vertex is at least
3 is ________?

Q Minimum number of vertices possible in a simple graph if 41 edges and degree of each
vertex is at most 5?

Q Which of the following degree sequence represent a simple non-directed graph?

1) {2, 3, 3, 4, 4, 5}
2) {2, 3, 4, 4, 5}
3) {3, 3, 3, 1}
4) {1, 3, 3, 4, 5, 6, 6}
5) {2, 3, 3, 3, 3}
6) {6, 6, 6, 6, 4, 3, 3, 0}
7) {6, 5, 5, 4, 3, 3, 2, 2, 2}
Q The following lists are the degrees of all the vertices of a graph : then (NET-DEC-2004)
(i) 1, 2, 3, 4, 5 (ii) 3, 4, 5, 6, 7 (iii) 1, 4, 5, 8, 6 (iv) 3, 4, 5, 6
a) (i) and (ii) b) (iii) and (iv) c) (iii) and (ii) d) (ii) and (iv)

Q The degree sequence of a simple graph is the sequence of the degrees of the nodes in the
graph in decreasing order. Which of the following sequences cannot be the degree sequence
of any graph? (GATE-2010) (2 Marks)
I. 7, 6, 5, 4, 4, 3, 2, 1 II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2 IV. 8, 7, 7, 6, 4, 2, 1, 1
(A) I and II (B) III and IV (C) IV only (D) II and IV
Answer: (D)

Q An ordered n-tuple (d1, d2, …, dn) with d1 >= d2 >= ⋯ >= dn is called graphic if there exists a
simple undirected graph with n vertices having degrees d1, d2, …, dn respectively. Which of
the following 6-tuples is NOT graphic? (GATE-2014) (2 Marks)
(A) (1, 1, 1, 1, 1, 1) (B) (2, 2, 2, 2, 2, 2)
(C) (3, 3, 3, 1, 0, 0) (D) (3, 2, 1, 1, 1, 0)
Answer: (C)
 Some Popular Graph
• Bi-partite graph: - A graph G(V, E) is called bi-partite graph if it’s vertex set V(G) can be
partitioned into two non-empty disjoint subset V1(G) and V2(G) in such a way that each
edge e ϵ E(G) has it’s one end point in V1(g) and other end point in V2(g). The partition V
= V1 U V2 is called bipartition of G.
• Complete Bi-partite graph: - A Bi-partite graph G(V, E) is called Complete bi-partite
graph if every vertex in the first partition is connected to every vertex in the second
partition, denoted by Km,n.
• Cycle Graph: - A cycle graph or circular graph is a graph that consists of a single cycle, or
in other words, some number of vertices (at least 3) connected in a closed chain. The
cycle graph with n vertices is called Cn. The number of vertices in Cn equals the number
of edges, and every vertex has degree 2; that is, every vertex has exactly two edges
incident with it.
• Wheel graph: - A wheel graph is a graph formed by connecting a single universal
vertex to all vertices of a cycle. Some authors write Wn to denote a wheel graph
with n vertices (n ≥ 4); other authors instead use Wn to denote a wheel graph with n+1
vertices (n ≥ 3), which is formed by connecting a single vertex to all vertices of a cycle of
length n.
Q the graph K3,4 has: (NET-DEC-2008)
a) 3 edges b) 4 edges c) 7 edges d) 12 edges

Q Consider the graph given below: (NET-DEC-2015)

The two distinct sets of vertices, which make the graph bipartite are:
a) (v1, v4, v6); (v2, v3, v5, v7, v8) b) (v1, v7, v8); (v2, v3, v5, v6)
c) (v1, v4, v6, v7); (v2, v3, v5, v8) d) (v1, v4, v6, v7, v8); (v2, v3, v5)
Answer: (C)
 Complement of a Graph
• The complement of a simple graph G (V, E) is a graph Gc (V, E) on the same vertices set
as of G, such that there will be an edge between two vertices u, v in Gc if and only if
there is no edge between u, v in G. i.e. two vertices of Gc are adjacent if they are not
adjacent in G.
• V(G) = V(Gc)
• E(Gc) = {(u, v) | (u, v) ∉ E(G)}
• E(Gc) = E(Kn) - E(G)

Properties

• G U Gc = Kn
• G ⋂ Gc = null graph
• |E(G)| + |E(Gc)| = E(Kn) = n(n-1)/2

Q A simple graph G has 30 edges and Gc has 36 edges, the number of vertices in G will be?

Q a simple graph G has |v|=8 and |E|=12, find number of edges in |E(Gc)|?

Q A simple graph G has 56 edges and Gc has 80 edges, the number of vertices in G will be?
 Traversal
Walk / Edge Train / Chain: -A Walk is defined as a finite alternating sequence of vertices and
edges, beginning and ending with vertices, such that each edge is incident with the vertices
preceding and following it. No edge is allowed to appear more than once in a walk. A vertex,
however, may appear more than once.

Traversal Walk Open Walk Closed Walk Path

V1 g V3 b V2 e V4 d V3 b V2
V1 a V2 e V4 d V3 b V2 V5
V1 g V3 c V3 b V2 a V1
V1 a V2 b V3 d V4 h V5

• Vertices with which a walk begins and ends are called its terminal vertices. It is possible
for a walk to begin and end at the same vertex. Such a walk is called a closed walk. A
walk that is not closed is called an open walk.
• An open walk in which no vertex appears more than once is called a path (a path does
not interact itself). Number of edges in a path is called length of a path.

Connected Graph: A graph is said to be connected if there is at one path between every pair of
vertices in G.

• A graph with n vertices can be connected with minimum n -1 edges.

• A graph with n vertices will necessary be connected if it has more than (n - 1) (n - 2)/2
edges.
 • if a graph (connected or disconnected) has exactly two vertices of odd degree, there
must be a path joining these two vertices

Q Which condition is necessarily for a graph to be connected?

a) A graph with 6 vertices and 10 edges
b) A graph with 7 vertices and 14 edges
c) A graph with 8 vertices and 22 edges
d) A graph with 9 vertices and 28 edges

Q A simple graph G with n-vertices is connected if the graph has (NET-SEP-2013)

(A) (n – 1) (n – 2)/2 edges (B) More than (n – 1) (n – 2)/2 edges
(C) Less than (n – 1) (n – 2)/2 edges (D) ∑ki=1 C(ni, 2) edges

Q Consider an undirected graph G with 100 nodes. The maximum number of edges to be
included in G so that the graph is not connected is (NET-SEP-2013)
(A) 2451 (B) 4950 (C) 4851 (D) 9900
 Euler Graph
Euler Graph: - If some closed walk in a graph contains all the edges of the graph(connected),
then the walk is called a Euler line and the graph a Euler Graph.

• A given connected graph G is a Euler graph if and only if all vertices of G are of even
degree.

• A connected graph G is Eulerian if and only if its edge set can be decomposed into
cycles.

• The number of edge−disjoint paths between any two vertices of an Euler graph is even.

• An open walk that includes (or traces) all edges of a graph without retracing any edge is
called a unicursal line or open Euler line. A connected graph that has a unicursal line is
called a unicursal graph.

• Clearly by adding an edge between the initial and final vertices of a unicursal line, we
get an Euler line.

Q G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and
make it adjacent to each odd degree vertex of G. The resultant graph is sure to be (GATE-
2008) (2 Marks)
(A) regular (B) Complete (C) Hamiltonian (D) Euler
Answer: (D)

Q An undirected graph possesses an eulerian circuit if and only if it is connected and its vertices
are (NET-DEC-2010)
(A) all of even degree (B) all of odd degree
(C) of any degree (D) even in number
a) (a) only b) (b) and (c) c) (c) only d) (d) only
Answer: (D)

Q Given the following graphs: (NET-AUG-2016)

Which of the following is correct?

a) G1 contains Euler circuit and G2 does not contain Euler circuit.
b) G1 does not contain Euler circuit and G2 contains Euler circuit.
c) Both G1 and G2 do not contain Euler circuit.
d) Both G1 and G2 contain Euler circuit.
Answer: (C)

Q Which of the following graphs has a Eulerian circuit? (GATE-2007) (2 Marks)

(A) Any k-regular graph where k is an even number.
(B) A complete graph on 90 vertices
(C) The complement of a cycle on 25 vertices
(D) None of the above
Answer: (C)
 Hamiltonian

Hamiltonian Graph: - A Hamiltonian circuit in a connected graph is defined as a closed walk

that traverses every vertex of G exactly once, except of course the starting vertex, at which the
walk also terminates. A graph containing Hamiltonian circuit is called Hamiltonian graph.

• Finding weather a graph is Hamiltonian or not is a NCP problem.

• If we remove any one edge from a Hamiltonian circuit, we are left with a path. This path
is called a Hamiltonian path.
• If a graph has Hamiltonian circuit then it also has Hamiltonian path, but vice versa is not
true.
• In a complete graph with n vertices there are (n - 1)/2 edge-disjoint Hamiltonian circuits,
if n is odd number >= 3
• A sufficient (but by no means necessary) condition for a simple graph G to have a
Hamiltonian circuit is that the degree of every vertex in G be at least n/2, where n is the
number of vertices in G. (if this condition satisfy graph will be Hamiltonian but to be a
Hamiltonian graph this condition is not required to be true)

Q Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of
different Hamiltonian cycles in G is equal to (GATE-2019) (2 Marks)
(A) n! (B) n – 1! (C) 1 (D) (n-1)! / 2
Answer: (D)
A simple circuit in a graph G that passes through every vertex exactly once is called
a Hamiltonian circuit.
In an undirected complete graph on n vertices, there are n permutations are possible to visit
every node. But from these permutations, there are: n different places (i.e., nodes) you can
start; 2 (clockwise or anticlockwise) different directions you can travel.
So any one of these n! cycles is in a set of 2n cycles which all contain the same set of edges. So
there are,
= (n)! / (2n)
= (n−1)! / 2 distinct Hamilton cycles.

Q Consider a complete bipartite graph km,n. For which values of m and n does this, complete
graph have a Hamilton circuit (NET-JUNE-2014)
(A) m = 3, n = 2 (B) m = 2, n = 3 (C) m = n > 2 (D) m = n > 3
Q for which values of m and n does the complete bipartite graph km,n have a Hamilton circuit?
(NET-JULY-2019)
a) m! = n, m, n >=2 b) m! = n, m, n>=3
c) m = n, m, n>=2 d) m = n, m, n>=3

Q Consider the graph shown below:

This graph is a _______ (NET-DEC-2014)

a) Complete graph b) Bipartite graph

c) Hamiltonian graph d) All of the above

Q Which of the following statement(s) is/are false? (NET-DEC-2015)

(a) A connected multigraph has an Euler Circuit if and only if each of its vertices has even
degree.
(b) A connected multigraph has an Euler Path but not an Euler Circuit if and only if it has
exactly two vertices of odd degree.
(c) A complete graph (Kn) has a Hamilton Circuit whenever n ≥ 3.
(d) A cycle over six vertices (C6) is not a bipartite graph but a complete graph over 3 vertices is
bipartite.
Answer: (D)

Q Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is
true with respect to this Graph (G)? (NET-JUNE-2015) (NET-JAN-2017) (NET-DEC-2018)
(a) deg (v) ≥ n / 2 for each vertex of G
(b) |E(G)| ≥ 1 / 2 (n - 1) (n - 2) + 2 edges
(c) deg (v) + deg (w) ≥ n for every v and w not connected by an edge.
a) (a) and (b) b) (b) and (c) c) (a) and (c) d) (a), (b) and (c)
Answer: (C)
In an Hamiltonian Graph (G) with no loops and parallel edges: According to Dirac's theorem
in a n vertex graph, deg (v) ≥ n / 2 for each vertex of G. According to Ore's theorem deg (v) +
deg (w) ≥ n for every n and v not connected by an edge is sufficient condition for a graph to
be hamiltonian. If |E(G)| ≥ 1 / 2 * [(n - 1) (n - 2)] then graph is connected but it doesn't
guaranteed to be Hamiltonian Graph. (a) and (c) is correct regarding to Hamiltonian Graph.

Q if a graph(g) has no loops or parallel edges, and if the number of vertices(n) in the graph is
n>=3 , then graph G is Hamiltonian if (NET-DEC-2018)
(i) deg(v) ≥ n/3 for each vertex v
(ii) deg(v) + deg(w) ≥ n whenever v and w are not connected by an edge.
(iii) |E(G)| ≥ 1/3(n–1)(n–2) + 2
a) (i) and (iii) only b) (ii) only c) (ii) and (iii) only d) (ii) only
 Planer Graph
Planer Graph: - A graph is called a planer graph if it can be drawn on a plan in such a way that
no edges cross each other, otherwise it is called non-planer.
Application: civil engineering, circuit designing
Q Which of the following graphs is/are planner? (GATE-19) (2 Marks)
a) G1 only b) G1 and G2
c) G2 only d) G2 and G3
Answer: (C)

Q Which one of the following graphs is NOT planar? (GATE-2005) (2 Marks)

(A) G1 (B) G2 (C) G3 (D) G4

Answer: (A)

Q (GATE-2010) (2 Marks)

(A) K4 is planar while Q3 is not (B) Both K4 and Q3 are planar

(C) Q3 is planar while K4 is not (D) Neither K4 nor Q3 are planar
Answer: (B)

Q Two graphs A and B are shown below: Which one of the following statements is true? (NET-
DEC-2015)
a) Both A and B are planar b) Neither A nor B is planar
c) A is planar and B is not d) B is planar and A is not

Q G1 and G2 are two graphs as shown: (NET-JUNE-2012)

a) Both G1 and G2 are planar graphs

b) Both G1 and G2 are not planar graphs
c) G1 is planar and G2 is not planar
d) G1 is not planar and G2 is planar
 Simplest Non-Planer Graphs
• Kuratowski’s case I: - K5
• Kuratowski’s case II: - K3,3
• Both are simplest non-planer graph
• Both are regular graph
• If we delete either an edge or a vertex from any of the graph, they will become
planer

Q Let G be the non-planar graph with the minimum possible number of edges. Then G has
(GATE-1992) (1 Marks) (GATE-2007) (1 Marks)
(A) 9 edges and 5 vertices (B) 9 edges and 6 vertices
(C) 10 edges and 5 vertices (D) 10 edges and 6 vertices
Answer: (B)

Q A graph is planar if and only if, (GATE-1990) (2 Marks)

a) It does not contain subgraphs homeomorphic to k5 and k3,3.
b) It does not contain subgraphs isomorphic to k5 or k3,3.
c) It does not contain a subgraph isomorphic to k5 or k3,3
d) It does not contain a subgraph homeomorphic to k5 or k3,3.
Answer: (D)

Q A graph is non-planar if and only if it contains a subgraph homomorphic to (NET-DEC-2013)

(A) K3, 2 or K5 (B) K 3, 3 and K6 (C) K 3, 3 or K5 (D) K2, 3 and K5

How to find weather a graph is planer or non-planer

• A finite graph is planar if and only if it does not contain a subgraph that is
a subdivision(homorphism) of the complete graph K5 or the complete bipartite graph. In
practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given
graph is planar.
• A finite graph is planar if and only if it does not have K5 or K3,3 as a minor. A minor of a
graph results from taking a subgraph and repeatedly contracting an edge into a vertex,
with each neighbor of the original end-vertices becoming a neighbor of the new vertex.
(Wanger’s theorem)
 Further Analysis
• A planer graph divides the plane into number or regions (faces, planer embedding),
which are further divided into bounded(internal) and unbounded region(external).
• Euler's formula states that if a finite, connected, planar graph with v is the number of
vertices, e is the number of edges and r is the number of faces (regions bounded by
edges, including the outer, infinitely large region), then
r=e–v+2
• Euler's formula can be proved by mathematical induction

• Euler's formula (Disconnected graph): V – e + r – k = 1

Q suppose that a connected planar graph has six vertices, each of degree four, into how many
regions is the plane divided by a planner representation of this graph? (NET-JULY-2019)
a) 6 b) 8 c) 12 d) 20

Q Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number
of faces in the planar embedding of the graph is (GATE-2005) (2 Marks)
(A) 6 (B) 8 (C) 9 (D) 13
Answer: (B)

Q 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
(GATE-2012) (1 Marks)
(A) 3 (B) 4 (C) 5 (D) 6
Answer: (D)
 Other formula derived from Euler’s formula
• Connected planar graphs with more than one edge obey the inequality 2e>=3r , because
each face has at least three face-edge incidences and each edge contribute exactly two
incidences.
• Degree of the region is number of edges covering the region. Sum of degree of
regions = 2|E|
• Using r = e – v + 2 and 3r<=2e, eliminating r we get, e ≤ 3v – 6
• Using r = e – v + 2 and 3r<=2e, Eliminating e we get, r ≤ 2v − 4
Q maximum number of edges in a planar graph with n vertices (GATE-1992) (1 Marks)
Answer: 3n-6
Explanation: For a simple, connected, planar graph with v vertices and e edges, the following
simple conditions hold: If v ≥ 3 then e ≤ 3v − 6;

Q A graph G = (V, E) satisfies |E| ≤ 3 |V| – 6. The min-degree of G is defined as

. Therefore, min-degree of G cannot be (GATE-2003) (2 Marks)

(A) 3 (B) 4 (C) 5 (D) 6
Answer: (D)
Let the min-degree of G be δ(G), then G has at least |v| * δ(G) /2 edges.
|v|* δ(G) /2 <= 3*|v| - 6
|v|* δ(G) /2 - 3*|v| <= -6
for δ(G) = 6, we get 0 <= -6, Therefore, min degree of G cannot be 6.
Hence answer is (D).
Q Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices
with δ ≥ 3, which one of the following is TRUE? (GATE-2014) (2 Marks)
(A) In any planar embedding, the number of faces is at least n/2 + 2
(B) In any planar embedding, the number of faces is less than n/2 + 2
(C) There is a planar embedding in which the number of faces is less than n/2 + 2
(D) There is a planar embedding in which the number of faces is at most n/( δ +1)
Answer: (A)
This is the planar graph with minimum degree 33 for each vertex.
From this graph, we can say that 3n≤2e→(1)3n≤2e→(1)
As per Euler's formla :n−e+f=2⟹e=n+f−2→(2):n−e+f=2⟹e=n+f−2→(2)
From (1)(1) and (2)(2)
n+f−2≥3n2n+f−2≥3n2
⟹f≥3n2−n+2⟹f≥3n2−n+2
⟹f≥n2+2⟹f≥n2+2 (No of faces is at-least (n2+2) )
 Graph Coloring
• Graph coloring can be of two types vertex coloring and edge coloring.
• Associating a color with each vertex of the graph is called vertex coloring.
• Proper Vertex coloring: - Associating all the vertex of a graph with colors such that no
two adjacent vertices have the same color is called proper vertex coloring.
• Chromatic number of the graph: - Minimum number of colors required to do a proper
vertex coloring is called the chromatic number of the graph, denoted by χ(G). the graph
is called K-chromatic or K-colorable.
• Cost of finding chromatic number is an NPC problem and there exists no polynomial
algorithm to do that. There exists some greedy approach which try to solve it in P time,
but they do not guarantee optimal solution.
• Trivial graph is 1-chromatic
• A graph with 1 or more edge is at least 2-chromatic
• A complete graph Kn is n-chromatic
• Tree is always 2-chromatic
• Bi-partite graph is 2-chromatic
• Cn is 2-chromatic if n is even, Cn is 3-chromatic if n is odd
• 5-color theorem-any planer graph is at most 5-chromatic
• 4-colour theorem/hypothesis- any planer graph is 4-chromatic
• If Δ(G) is the maximum degree of any vertex in a graph then, χ(G) <= 1 + Δ(G)

Q What is the chromatic number of the following graph? (GATE-2008) (1 Marks)

(A) 2 (B) 3 (C) 4 (D) 5
Answer: (b)

Q The chromatic number of the following graph is _______(GATE-2018) (2 Marks)

Answer: (3)

Q The minimum number of colors required to color the following graph, such that no two
adjacent vertices are assigned the same color, is (GATE-2004) (2 Marks)

(A) 2 (B) 3 (C) 4 (D) 5

Answer: (C)

Q The minimum number of colors that is sufficient to vertex color any planar graph is
_______________(GATE-2016) (1 Marks)
Answer: (4)

Q What is the chromatic number of an n-vertex simple connected graph which does not
contain any odd length cycle? Assume n >= 2. (GATE-2009) (1 Marks)
(A) 2 (B) 3 (C) n-1 (D) n
Answer: (A)

Q The minimum number of colors required to color the vertices of a cycle with η nodes in such
a way that no two adjacent nodes have the same color is (GATE-2002) (1 Marks)
(A) 2 (B) 3 (C) 4 (D) n – 2⌊n/2⌋ + 2
Answer: (D)
Explanation: We need 3 colors to color a odd cycle and 2 colors to color an even cycle.
Q The number of colors required to properly color the vertices of every planer graph is (NET-
JUNE-2012)
a) 2 b) 3 c) 4 d) 5

Q In k-coloring of an undirected graph G = (V, E) is a function

c: V → {0, 1, …, K-1} such that c(u) !=c (v) for every edge (u,v) ∈ E.
Which of the following is not correct? (NET-DEC-2018)
a) G is bipartite
b) G is 2-colorable
c) G has cycles of odd length
d) G has no cycles of odd lengt
 Tree
A tree is a connected graph without any circuit.

• There is one and only one path between every pair of vertices in a tree
• If in a graph G, there is one and only one path between every pair of vertices then G is a
tree
• A tree with n vertices has n-1 edges
• Any connected graph with n vertices and n-1 edges in a tree
• A graph is a tree if and only if it is minimally connected
• A graph G with n vertices and n-1 edges and no circuit is connected

Eccentricity: - Eccentricity of a vertex is denoted by E(v) of a vertex v in a graph G, it is the

distance from V to the vertex farthest from V in G. E(v) = max d(v, vi) vi ϵ G

• A vertex with minimum eccentricity in a tree T is called center of T.

• Minimum eccentricity of any vertex in a tree T is called radius of tree. (eccentricity of
center)
• Maximum eccentricity of any vertex in a tree T is called diameter of tree. (length of the
longest path)
• Every tree has either one or two centers.
Q Consider the tree given below: (NET-DEC-2012)
Using the property of eccentricity of a vertex, find every vertex that is the center of the given
tree:

a) d & h b) c & k c) g, b, c, h, i, m d) c & h

Q T is a graph with n vertices. T is connected and has exactly n-1 edges, then: (NET-DEC-2005)
a) T is a tree
b) T contains no cycles
c) Every pairs of vertices in T is connected by exactly one path
d) All of these

Q What is the maximum number of edges in an acyclic undirected graph with n vertices?
(GATE-2004) (1 Marks)
(A) n-1 (B) n (C) n + 1 (D) 2n-1
Answer: (A)

Q The minimum number of edges in a connected graph with ‘n’ vertices is equal to (NET-DEC-
2010)
(A) n (n – 1) (B) n (n – 1)2 (C) n2 (D) n – 1

Q which of the following statement is false? (NET-JUNE-2006)

a) Every tree is a bipartite graph
b) A tree contains a cycle
c) A tree with n nodes contains (n-1) edges
d) A tree is connected graph

Q Which of the following does not define a tree? (NET-JUNE-2008)

a) a tree is a connected acyclic graph.
b) A tree is a connected graph with n-1 edges where ‘n’ is the number of vertices in the graph.
c) A tree is an acyclic graph with n-1 edges where ‘n’ is the number of vertices in the graph.
d) A tree is a graph with no cycles.

Q which two of the following are equivalent for an undirected graph G? (NET-JUNE-2009)
i) G is a tree
ii) There is at least one path between any two distinct vertices of G
iii) G contains no cycles and has (n-1) edges
iv) G has n edges
a) (i) and (ii) b) (i) and (iii) c) (i) and (iv) d) (ii) and (iii)

Q Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.
(GATE-2017) (1 Marks)
Answer: (18)

Q A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree
2. If the other vertices have degree 1, how many vertices are there in the graph? (NET-DEC-
2014)
a) 5 b) n–3 c) 20 d) 11

Q Consider the undirected graph G defined as follows. The vertices of G are bit strings of
length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly
one-bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of
the chromatic number of G to the diameter of G is (GATE-2006) (2 Marks)
(A) 1/(2n-1) (B) 1/n (C) 2/n (D) 3/n
Answer: (C)
Q How many edges are there in a forest of t-trees containing a total of n vertices? (NET-DEC-
2013)
(A) n + t (B) n – t (C) n ∗ t (D) nt

Q A tree with n vertices is called graceful, if its vertices can be labeled with integers 1, 2,....n
such that the absolute value of the difference of the labels of adjacent vertices are all
different. Which of the following trees are graceful? (NET-DEC-2015)

a) (a) and (b) b) (b) and (c) c) (a) and (c) d) (a), (b) and (c)
Ans: D
 Spanning tree
• A tree T is said to be spanning tree of a connected graph G, if T is a subgraph of G and T
contains all vertices of G.
• An edge in a spanning tree T is called a branch of T
• An edge that is not in the given spanning tree T is called a chord.
• Branch and Chord are defined with respect to a given spanning tree.
• With respect to any of its spanning tree, a connected graph of n vertices and e edges
has n-1 branches and e-n+1 chord
• A connected graph G is a tree if and only if adding an edge between any two vertices
in g creates exactly one cycle.
• Rank(r) = n-1
• Nullity(µ) = e – n + 1
• Rank + nullity = number of edges in G

Spanning Forest: - if a graph is not connected, then there is no possibility of finding a spanning
tree, but we can find a spanning forest. If a graph is not connected then we can find connected
components, finding a spanning tree in each component we can find spanning forest.

• A disconnected graph with K components has a spanning forest consisting of K spanning

tree.
 • Nullity(µ) = e – n + k
• Rank(r) = n-k
• Rank + nullity = number of edges in G

Fundamental circuit: - With respect to a spanning tree T in a connected graph G, adding any
one chord to T will create exactly one circuit such a circuit formed by adding a chord to a
spanning tree is called fundamental circuit.

Q for a complete graph with N vertices, the total number of spanning tree is given by: (NET-
DEC-2006)
a) 2N-1 b) NN-1 c) NN-2 d) 2N+1
Q How many edges must be removed to produce the spanning forest of a graph with N
vertices, M edges and C connected components? (NET-JUNE-2013)
(A) M+N–C (B) M–N–C (C) M–N+C (D) M+N+C

Q Which of the following connected simple graph has exactly one spanning tree? (NET-JUNE-
2013)
(A) Complete graph (B) Hamiltonian graph
(C) Euler graph (D) None of the above

Q The number of different spanning trees in complete graph, K4 and bipartite graph, K2,2
have ______ and _______ respectively. (NET-JULY-2016)
a) 14, 14 b) 16, 14 c) 16, 4 d) 14, 4
Ans. C
 Cut-Set (edge and vertex connectivity)
Cut-Set (Edges)

Cut Set: - In a connected graph G, a cut set is a set of edges whose removal from g leaves G
disconnected, provided removal of no proper subset of these edges disconnects G.

Q which of the following set of edges is a valid cut set?

Cut Set Validity Reason

{a, f, g}
{a, e, h, c}
{a, i}
{e, h, f, g}
{d, h, c, g}
{d, e, f}
• Every Cut Set in a connected graph G must contain at least one branch of every
spanning tree of G.
• Every circuit has an even number of edges in common with any Cut-Set.
• Connectivity: - each cut-set of a connected graph G consist of a certain number of
edges. The number of edges in the smallest cut-set is defined as the edges connectivity
of G. It is denoted by λ(G).
• if the edge connectivity from a graph is one, then that edge how’s removal disconnect
the graph is called a bridge.
 Cut-Set (Vertex)
Cut Set: - In a connected graph G, a cut set is a set of vertices whose removal from g leaves G
disconnected, provided removal of no proper subset of these vertices disconnects G.

Q which of the following set of edges is a valid cut set?

Cut Set Validity Reason

{5, 3}
{6}
{5, 2}
{2}
{1, 5, 3}
Vertex Connectivity: - Each cut-set of a connected graph G consist of a certain number of
vertices. The number of vertices in the smallest cut-set is defined as the vertex connectivity of
G. It is denoted by k(G).
• A connected graph is said to be separable of its vertex connectivity is one.
• If the vertex connectivity of a graph is one, then that vertex how removal disconnects a
graph is called articulation point.
• Km, n, Cn, Kn

,
Q if G is a forest with n vertices and k connected components, how many edges does G have?
(GATE-2014) (2 Marks)
(A) floor(n/k) (B) ceil(n/k) (C) n-k (D) n-k+1
Answer: (C)

Q The maximum number of possible edges in an undirected graph with ‘a’ vertices and ‘k’
components is ______. (GATE-1991) (2 Marks)
Answer: ((a-k+1)(a-k))/2

Hence the maximum is achieved when only one of the components has more than one vertex.
How many vertices does this graph have? the big component has n−k+1n−k+1 vertices and is
the only one with edges. So it has (n−k+1)(n−k)2 edges.

Q 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? (GATE-2008) (2 Marks)
(A) For every subset of k vertices, the induced subgraph has at most 2k-2 edges
(B) The minimum cut in G has at least two edges
(C) There are two edge-disjoint paths between every pair to vertices
(D) There are two vertex-disjoint paths between every pair of vertices
Answer: (D)
Q Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G,
the number of components in the resultant graph must necessarily lie between(GATE-2003) (1
Marks) (k-1)(n-1)
(A) k and n (B) k – 1 and k + 1
(C) k – 1 and n – 1 (D) k + 1 and n – k
Answer: (A)
Explanation: Minimum: It may be possible that the removed vertex doesn’t disconnect its
component. Maximum: It may be possible that the removed vertex disconnects all
components. For example the removed vertex is center of a star.

Q Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of
the numbers 1, 2, …, 100. There is an edge between vertices u and v if and only if the label of u
can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree
of a vertex in G, and z denote the number of connected components in G. Then y + 10z =
_______. (GATE-2018) (2 Marks)
Answer: (109)

G is a graph with 100! vertices. Label of each vertex obtains from distinct permutation of
numbers “1, 2, … 100”.
There exists an edge between two vertices iff label of ‘u’ is obtained by swapping two adjacent
numbers in label of ‘v’.
Example:
12 & 21, 23 & 34
The sets of the swapping numbers be (1, 2) (2, 3) (3, 4) … (99).
The no. of such sets are 99 i.e., no. of edges = 99.
As this is regular, each vertex has ‘99’ edges correspond to it.
So degree of each vertex = 99 = y.
As the vertices are connected together, the number of components formed = 1 = z
y + 102 = 99 + 10(1) = 109 )

Q Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then
which one of the following graphs has the same strongly connected components as G? (GATE-
2014) (1 Marks)
a) G1 = (V,E1) where E1={(u, v)∣(u, v)∉E}
b) G2 = (V,E2) where E2={(u, v)∣(v, u)∈E}
c) G3 = (V,E3) where E3={(u, v)∣ there is a path of length ≤2 from u to v in E}
d) G4 = (V4,E) where V4 is the set of vertices in G which are not isolated
Answer: (B)

(A) is false. Consider just two vertices connected to each other. So, we have one SCC. The new
graph won't have any edges and so 22 SCC.
(B) is true. In a directed graph an SCC will have a path from each vertex to every other vertex.
So, changing the direction of all the edges, won't change the SCC.
(D) is false. Consider any graph with isolated vertices- we loose those components.
(C) is a bit tricky. Any edge is a path of length 11. So, the new graph will have all the edges
from old one. Also, we are adding new edges (u,v)(u,v). So, does this modify any SCC? No,
because we add an edge (u,v)(u,v), only if there is already a path of
length <=2<=2 from uu to vv- so we do not create a new path. So, both (B) and (C) must
answer, though GATE key says only B.
 Isomorphism
• In general, two graphs are said to be isomorphic if they are perhaps the same graphs,
but just drawn differently with different names. i.e. two graphs are thought of as
isomorphic if they have identical behavior in terms of graph-theoretic properties.
• Formally speaking: - Two graphs G and G’ are said to be isomorphic, if there is a one to
one correspondence between their vertices and between their edges such that the
incidence relationship is preserved.

• More Formally speaking: Two graph G1(V1,E1) and G2(V2,E2) are isomorphism to each
other if there is a bijection function :
ƒ: V1(G1) → V2(G2)
• such that any two vertices u, v ϵ V1(G1), if u, v ϵ E1(G1) iff (ƒ(u), ƒ(v)) ϵ E2(G2)
• i.e. if u,v are adjacent in G1 then, ƒ(u) and ƒ(v) will be adjacent in G2.

• Time Complexity two find weather two graphs are isomorphic or not Determining if
two graphs are isomorphic is thought to be neither an NP-complete problem nor a P-
problem, although this has not been proved (Skiena 1990, p. 181). In fact, there is a
famous complexity class called graph isomorphism complete which is thought to be
entirely disjoint from both NP-complete and from P.

Q How many simple non isomorphic graphs are possible with 3 vertices?

Q How many simple non isomorphic graphs are possible with 4 vertices and 2 edges?

Q How many simple non isomorphic graphs are possible with 4 vertices and 3 edges?

Q How many simple non isomorphic graphs are possible with 5 vertices and 3 edges?

Q How many simple non isomorphic graphs are possible with 6 vertices and 6 edges, such that
degree of every vertex must be same?

Q How many simple non isomorphic graphs are possible with 8 vertices and 8 edges, such that
degree of every vertex must be same?
How to check weather two graphs are isomorphic or not

• Number of vertices
• Number of edges
• Number of vertices with a given degree
• Check degree property of vertices with their neighbor
• Check minimum cycle length, maximum cycle length, or number of cycles with a specific
length
• Can check isomorphism for complement of the graph
• Planer, non-planer
• Connected disconnected
• Chromatic number
• Matching number, covering number
• Edge connectivity, vertex connectivity

If it seems that graphs are isomorphic to each other than identify the similar vertex and delete
both, and keep repeating the process until we are sure.
Q Which of the following graphs is isomorphic to (GATE-2012) (2 Marks)
Answer: (B)

Q (NET-JUNE-2014)
Q A graph is self-complementary if it is isomorphic to its complement. For all self-
complementary graphs on n vertices, n is (GATE-2015) (2 Marks)
(A) A multiple of 4 (B) Even
(C) Odd (D) Congruent to 0 mod 4, or 1 mod 4
Answer: (D)

Q A cycle on n vertices is isomorphic to its complement. The value of n is _____. (GATE-2014)

(2 Marks)
Answer: (5)
 Matching and covering
Matching: - Let G be a graph, a subgraph M of G is called a matching of G, if every vertex of G
is incident with at most one edge in M.

deg(v) <= 1, ∀v VϵV(G)

M1 M2 M3 M4

• In matching no two edges are adjacent.

Maximal Matching: - A matching M of a graph G is said to be maximal, if no other edges of G

can be added to M, without violating the deg condition.
Maximum Matching: - A matching of a graph with maximum no of edges is called a maximum
matching of G.

• Number of edges in a maximum matching of G is called matching number.

Perfect Matching: - A matching of a graph in which every vertex is matched is called perfect
matching.

• If a graph G has a perfect match then no of vertices in G is even.

• If no of vertexes is even, it is not necessary to have a perfect match.
• No of perfect matchings are there in a complete graph Kn is [(2n)!]/n!2n

Q How many perfect matchings are there in a complete graph of 6 vertices? (GATE-2003) (2
Marks)
(A) 15 (B) 24 (C) 30 (D) 60
Answer: (A)
 Covering
Line Covering: - Let G (V, E) be a graph, a subset C of E is called a line covering of G, if every
vertex of G is incident with at least one edge in C. (deg at least one)

deg(v) >= 1

C1 C2 C3 C4

• Line covering of a graph G does not exist if G has an isolated vertex.

Minimal Line covering: - A line covering is said to be minimal if no edge can be deleted from
the line covering, without destroying its ability to cover the graph.

Minimum line covering: - A line covering with minimum no of edges is called a minimum line
covering.

• No of edges in minimum line covering is called line covering number of a graph G,

denoted by α1
• line covering of a graph with n vertices contain at least lower bound(n/2) edges.
• no minimal line covering can contain a cycle.
Independent Line set: - Let G (V, E) be a graph, a subset L of E is called independent line
set of G, if no two edges are adjacent.

L1 = {(b, d)}
L2 = {(b, d), (e, f)}
L3 = {(a, d), (b, c), (e, f)}
L4 = {(a, b), (e, f)}

Maximal independent Line set: - An independent line set L of a graph G is said to be maximal
if no other edges of G can be added to L.

Maximum independent line set: - An independent line set L of a graph G, with maximum no of
edges is called maximum independent line set.

• No of edges in minimum independent line set is called independent number of G

denoted by β1.
line independent no = matching no of G
α1 + β1 = |v|
Vertex Covering: - Let G (V, E) be graph, a subset K of V is called a vertex coving of G. if
every edge of G is incident with a vertex in K.

K1 = {b, d}
K2 = {a, b, c}
K3 = {b, c, d}

Minimal vertex cover: - Vertex covering K of a graph G is said to be minimal if no vertex can be
deleted from K, without violating the condition.

Minimum vertex covering: - A vertex covering of a graph G with minimum number of vertices
is called as minimum vertex covering.

• No of vertices in a minimum vertex covering is called vertex Covering no of graph G

denoted by α2
Independent vertex set: - let G (V, E) be a graph, a subset S of V is called an
independent vertex set if no two vertices in S are adjacent.

S1 = {b}
S2 = {d, e}
S3 = {a, c}

Maximum independent Vertex Set: - An independent vertex set is said to be maximal, if no

other vertex of G can be added to the set.
S1 = {b}
S2 = {d, e}
S3 = {a, c, e}

Maximum independent vertex set: - An independent vertex set of graph G with maximum no
of vertices is called maximum independent vertex set.

• The number of vertices in maximum independent vertex set is called as vertex

independent number of G donated by β2
α2 + β2 = |V|

Q What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes?
(GATE-2008) (1 Marks)
(A) 5 (B) 4 (C) 3 (D) 2
Answer: (C)
Q A vertex cover of an undirected graph G(V, E) is a subset V1 ⊆ V vertices such that (NET-
JUNE-2013)
(A) Each pair of vertices in V1 is connected by an edge
(B) If (u, v) ∈ E then u ∈ V1 and v ∈ V1
(C) If (u, v) ∈ E then u ∈ V1 or v ∈ V1
(D) All pairs of vertices in V1 are not connected by an edge

Q Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover
of G is 8. Then, the size of the maximum independent set of G is (GATE-2005) (1 Marks)
(A) 12 (B) 8 (C) Less than 8 (D) More than 12
Answer: (A)

Q A clique in a simple undirected graph is a complete subgraph that is not contained in any
larger complete subgraph. How many cliques are there in the graph shown below? (NET-JULY-
2016)

a) 2 b) 4 c) 5 d) 6

Q In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of
the following statements is True? (GATE-2015) (2 Marks)
(A) A tree has no bridge
(B) A bridge cannot be part of a simple cycle
(C) Every edge of a clique with size ≥ 3 is a bridge (A clique is any complete subgraph of a
graph)
(D) A graph with bridges cannot have a cycle
Answer: (B)

Q A _________ complete subgraph and a _________ subset of vertices of a graph G = (V, E)

are a clique and a vertex cover respectively. (NET-DEC-2013)
(A) minimal, maximal (B) minimal, minimal
(C) maximal, maximal (D) maximal, minimal
 Function
A relation ‘f’ from a set ‘A’ to a Set ‘B’ is called a function, if each element of A is mapped
with a unique element on B.
f: A→B

Set A is called Domain and B is called Co-Domain

Range of f = {y | y ϵ B and (x, y) ϵ f}
Range of fun ⊑ B

If |A| = m and |B|= n, then number of functions possible from A to B = n m

Q The number of functions from an m element set to an n element set is (GATE-1998) (1

Marks)
a) m + n b) mn c) nm d) m * n
Answer: (C)

Q Suppose X and Y are sets and |X| and |Y| are their respective cardinalities. It is given that
there are exactly 97 functions from X to Y. From this one can conclude that (GATE-1996) (1
Marks)
(A) |X|=1, |Y|=97 (B) |X|=97, |Y|=1
(C) |X|=97, |Y|=97 (D) None of the above
Answer: (A)

Q Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X x Y. Let E be the set of all
subsets of W. The number of functions from Z to E is (GATE-2006) (1 Marks)
(A) Z2xy (B) Z x 2 xy (C) 2z (D) 2xyz
Answer: (D)

Q Let S denote the set of all functions f: {0,1}4 -> {0,1}. Denote by N the number of functions
from S to the set {0,1}. The value of Log2Log2N is ______. (GATE-2014) (2 Marks)
Answer: 16

Q 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 sets above are countable? (GATE-2018) (1 Marks)
(A) Q and S only (B) P and S only (C) P and R only (D) P, Q and S only
Answer- D

Q A function f:N+→N+, defined on the set of positive integers N+, satisfies the following
properties:
f(n)=f(n/2) if n is even
f(n)=f(n+5) if n is odd
Let R={i ∣ ∃j : f(j)=i} be the set of distinct values that f takes. The maximum possible size
of R is ___________. (GATE-2016) (2 Marks)
Ans: 2

Q Let X and Y be finite sets and f: X -> Y be a function. Which one of the following
statements is TRUE? (GATE-2014) (1 Marks)
a) For any subsets A and B of X,| f(A ∪ B)| = |f(A)| + |f(B)|
b) For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B)
c) For any subsets A and B of X,| f(A ∩ B)| = min{|f(A)|, |f(B)|}
d) For any subsets S and T of Y,f−1(S ∩ T) = f−1(S) ∩ f−1(T)
Answer: (D)

Let X = {a, b, c} and Y = {1, 2}

Let f(a) = 1, f(b) = 1, f(c) = 1 and A = {a}, B = {b, c}

A)
LHS: |f(A∪B)| = |f({a, b, c})|= |{1}| =1
RHS: |f(A)|+|f(B)| = 1+1 = |f(A)|+|f(B)| =1 + 1 = 2,

B)
LHS: f(A∩B) = f({})={}
RHS: f(A)∩f(B) = {1} ∩ {1} = {1}

C)
LHS: |f(A∩B)|=|f({})|=|{}|=0
RHS: min{|f(A)|,|f(B)|} = min(1,1) = 1

D) Its easy to see that this is true because in a function a value can be mapped only to one
value. The option assumes inverse of function ff exists.
Q Let f: A→B be a function, and let E and F be subsets of A. Consider the following
statements about images.
S1: f (E ∪ F) = f (E) ∪ f (F)
S2: f (E ∩ F) = f (E) ∩ f (F)
Which of the following is true about S1 and S2? (GATE-2001) (2 Marks)
(A) Only S1 is correct (B) Only S1 is correct
(C) Both S1 and S2 are correct (D) None of S1 and S2 is correct
Answer: (B)
 Function composition
fog(x) = f(g(x))
gof(x) = g(f(x))

Q If g(x) = 1−x and h(x)=x / (x−1), then g(h(x)) / h(g(x)) is: (GATE-2015) (1 Marks)
a) h(x) / g(x) b) −1 / x c) g(x) / h(x) d) x / (1−x)2
Answer: (a)

Q Let f and g be the functions from the set of integers defined by f(x)=2x+3 and g(x)=3x+2.
Then the composition of f and g and g and f is given as (NET-Jan-2013)
a) 6x+7, 6x+11 b) 6x+11, 6x+7
c) 5x+5, 5x+5 d) None of the above
Answer: (a)
 One-to-One (Injection)
A function F: A→B is said to be one-to-one function if every element of A has distinct image
in B. i.e. no two elements of the set B can have the same Pre-image in A.

If A and B are finite set, then one-to-one from A→B is possible

if |A| <= |B|

No of function possible = npm = P (n, m)

If |A| = |B| = n, then no of functions possible is n!

Q Let X and Y denote the sets containing 2 and 20 distinct objects respectively and F denote
the set of all possible functions defined from X and Y. Let f be randomly chosen from F. The
probability of f being one-to-one is _________ (GATE-2015) (2 Marks)
Answer: 0.95
 Onto (surjection)
A function f: A → B is said to be onto if and only if every element of B is mapped by at least
one element of A.

Range of f = B

If A and B are finite sets, then onto function from A→B is possible, |B|<=|A|

If |A| = |B|, then every onto function from A to B is also one-to-one function.

No of onto function possible from A to B

= nm – nc1(n-1)m + nc2(n-2)m - nc3(n-3)m +---------+ (-1)n nc n-1 1m

Q if n = 3 and m = 6, then no of onto function possible?

Q In a company an employee can be assigned to 4 projects so that each employee can be

assigned to only one point, every project should assign with at least one employee. Then
how many different assignments are possible?

Q The number of onto functions (surjective functions) from set X = {1, 2, 3, 4} to set Y = {a,
b, c} is ________________ (GATE-2015) (2 Marks)
Answer: 36

Q How many onto (or surjective) functions are there from an n-element (n >= 2) set to a 2-
element set? (GATE-2014) (2 Marks)
(A) 2n (B) 2n – 1 (C) 2n – 2 (D) 2(2n – 2)
Answer: (C)

Q Consider the set of all functions f: {0,1, … ,2014} → {0,1, … ,2014} such that f(f(i)) = i, for
all 0 ≤ i ≤ 2014. Consider the following statements: (GATE-2014) (2 Marks)
P. For each such function it must be the case that for every i, f(i)=i
Q. For each such function it must be the case that for some i, f(i)=i
R. Each function must be onto.
Which one of the following is CORRECT?
(A) P, Q and R are true (B) Only Q and R are true
(C) Only P and Q are true (D) Only R is true
Answer: (B)

Q Let f: B → C and g: A → B be two functions and let h = f o g. Given that h is an onto

function. Which one of the following is TRUE? (GATE-2005) (2 Marks)
(A) f and g should both be onto functions
(B) f should be onto but g need not be onto
(C) g should be onto but f need not be onto
(D) both f and g need not be onto
Answer: (B)

Q Let f be a function from a set A to a set B, g a function from B to C, and h a function from
A to C, such that h(a) = g(f(a)) for all a ∈ A. Which of the following statements is always true
for all such functions f and g? (GATE-2005) (2 Marks)
(A) g is onto => h is onto (B) h is onto => f is onto
(C) h is onto => g is onto (D) h is onto => f and g are onto
Answer: (C)
 Bijection
A function f: A→B is said to be bijection if f is one-to-one and onto.

Bijection from A and B is possible, if |A| = |B|

No of Bijection from A to B = n!

Inverse of a function
Let f: A→B, if the inverse relation f-1 from B to A is also a function f-1: B→A

Inverse of a function f: A→B exists, if f: A→B is a bijection.

Q Let R denote the set of real numbers. Let f: R×R→R×R be a bijective function defined by f
(x, y) = (x + y, x− y). The inverse function of f is given by (GATE-1996) (2 Marks)
a) f−1(x, y)=(1 / (x + y), 1 / (x − y))
b) f−1(x, y)=(x − y, x + y)
c) f−1(x, y)=( (x + y) / 2, (x – y) / 2)
d) f−1(x, y)=[2(x − y),2(x + y)]
Answer: (C)
Constant function: A function f: A→B is a constant function if f(x) = c, ∀x ϵ A

Identity function: A function f: A→A is called an identity function if

F(x) = x, ∀x ϵ A
Q For the set N of natural numbers and a binary operation f: N x N → N, an element z ∊ N is
called an identity for f, if f (a, z) = a = f (z, a), for all a ∊ N. Which of the following binary
operations have an identity? (GATE-2006) (1 Marks)
1. f (x, y) = x + y – 3 2. f (x, y) = max (x, y) 3. f (x, y) = xy
(A) I and II only (B) II and III only (C) I and III only (D) None of these
Answer: (A)