250+ TOP MCQs on Types of Set and Answers

Discrete Mathematics Multiple Choice Questions on “Types of Set”.

1. {x: x is an integer neither positive nor negative} is ________
a) Empty set
b) Non-empty set
c) Finite set
d) Non- empty and Finite set

Answer: d
Clarification: Set = {0} non-empty and finite set.

2. {x: x is a real number between 1 and 2} is an ________
a) Infinite set
b) Finite set
c) Empty set
d) None of the mentioned

Answer: a
Clarification: It is an infinite set as there are infinitely many real number between any two different real numbers.

3. Write set {1, 5, 15, 25,…} in set-builder form.
a) {x: either x=1 or x=5n, where n is a real number}
b) {x: either x=1 or x=5n, where n is a integer}
c) {x: either x=1 or x=5n, where n is an odd natural number}
d) {x: x=5n, where n is a natural number}

Answer: c
Clarification: Set should include 1 or an odd multiple of 5.

4. Express {x: x= n/ (n+1), n is a natural number less than 7} in roster form.
a) {12, 23, 45, 67}
b) {12, 23, 34, 45, 56, 67, 78}
c) {12, 23, 34, 45, 56, 67}
d) Infinite set

Answer: c
Clarification: n/(n+1) = 1/(1+1) = 12 and n>7.

5. Number of power set of {a, b}, where a and b are distinct elements.
a) 3
b) 4
c) 2
d) 5

Answer: b
Clarification: Power set of {a, b} = {∅, {a, b}, {a}, {b}}.

6. Which of the following is subset of set {1, 2, 3, 4}?
a) {1, 2}
b) {1, 2, 3}
c) {1}
d) All of the mentioned

Answer: d
Clarification: There are total 16 subsets.

7. A = {∅,{∅},2,{2,∅},3}, which of the following is true?
a) {{∅,{∅}} ∈ A
b) {2} ∈ A
c) ∅ ⊂ A
d) 3 ⊂ A

Answer: c
Clarification: Empty set is a subset of every set.

8. Subset of the set A= { } is?
a) A
b) {}
c) ∅
d) All of the mentioned

Answer: d
Clarification: Every set is subset of itself and Empty set is subset of each set.

9. {x: x ∈ N and x is prime} then it is ________
a) Infinite set
b) Finite set
c) Empty set
d) Not a set

Answer: a
Clarification: There is no extreme prime, number of primes is infinite.

10. Convert set {x: x is a positive prime number which divides 72} in roster form.
a) {2, 3, 5}
b) {2, 3, 6}
c) {2, 3}
d) {∅}

Answer: c
Clarification: 2 and 3 are the divisors of 72 which are prime.

250+ TOP MCQs on Special Sequences and Answers

Discrete Mathematics Multiple Choice Questions on “Special Sequences”.

1. Let the sequence be 1×2, 3×22, 5×23, 7×24, 9×25……… then this sequence is _________
a) An arithmetic sequence
b) A geometic progression
c) Arithmetico-geometric progression
d) None of the mentioned

Answer: c
Clarification: If a1, a2……… are in AP and b1, b2………. are in GP then a2b2, a2b2,……… are in AGP.

2. Let the sequence be 1×2, 3×22, 5×23, 7×24, 9×25……… then the next term of this AGP is given by _________
a) 10×26
b) 10×27
c) 11×26
d) None of the mentioned

Answer: c
Clarification: Since here a1, a2……… are in AP and b1, b2………. are in GP then a2b2, a2b2,……… are in AGP thus an = 11 and bn = 26.

3. The sum of the first n natural numbers is given by _________
a) n(n+1)/2
b) n(n-1)/2
c) n2(n+1)/2
d) None of the mentioned

Answer: a
Clarification: 1 + 2 + 3 + 4 +……n = (n/2)(1 + n) Since this is AP.

4. The sum of square of the first n natural numbers is given by _________
a) n(n+1)(2n+1)/6
b) n(n-1)/2(2n+1)
c) n2(n+1)(2n+1)/6
d) None of the mentioned

Answer: a
Clarification: 12 + 22 + 32 + 42 +……n2 = n(1+n)(2n+1)/6.

5. The sum of cubes of the first n natural numbers is given by _________
a) {n(n+1)/2}2
b) {n(n-1)/2}2
c) {n2(n+1)/2}2
d) None of the mentioned

Answer: a
Clarification: 13 + 23 + 33 + 43 +……+ n3 = {n(n+1)/2}2.

6. The series 1, 1, 1, 1, 1…….. is not an AGP.
a) True
b) False

Answer: b
Clarification: Since 1, 1, 1, 1, 1…….. is in Ap and in Gp as well, Therefore the given sequence is also an AGP.

7. If in an AGP the common ratio of GP is 1 then that sequence becomes an AP sequence.
a) True
b) False

Answer: a
Clarification: In AGP sequence if r = 1, then terms are ab, (a+d)b, (a+2d)b…. and so on thus it is AP with common differnce bd.

8. The sequence 1, 1, 1, 1, 1…. is?
a) Absolutely summable
b) Is not absolutely summable
c) Can’t say
d) None of the mentioned

Answer: b
Clarification: For limit n tending to infinity the sum also tends to infinity and thus it is not summable.

9. Which of the following is a Triangular number series?
a) 1, 3, 6, 9, 12, 15…..
b) 1, 3, 6, 10, 15, 21……
c) 1, 6, 12, 18, 24…..
d) none of the mentioned

Answer: b
Clarification: In triangular number sequence ith term is previous term+i, with first term as 1.

10. Which of the following is a fibonacci series?
a) 0, 1, 2, 3, 4…….
b) 0, 1, 1, 2, 3, 5……
c) 10, 12, 14, 16…….
d) none of the mentioned

Answer: b
Clarification: Fibonacci series is formed by adding previous two term starting from 0 and 1.

250+ TOP MCQs on Number Theory – Quadratic Residue and Pseudo Prime

Discrete Mathematics online quiz on “Number Theory – Quadratic Residue and Pseudo Prime”.

1. If there exist an integer x such that x2 ≡ q (mod n). then q is called ______________
a) Quadratic Residue
b) Linear Residue
c) Pseudoprime
d) None of the mentioned

Answer: a
Clarification: q is called quadratic residue if it is congruent to a perfect square modulo n.

2. If there exist no integer x such that x2 ≡ q (mod n). then q is called __________
a) Quadratic Residue
b) Quadratic Nonresidue
c) Pseudoprime
d) None of the mentioned

Answer: b
Clarification: q is called quadratic nonresidue if it is not congurent to a perfect square modulo n.

3. The Fermat’s little theorem for odd prime p and coprime number a is?
a) ap-1 ≡ 1 (mod p)
b) ap-1 ≡ 7 (mod p)
c) ap(2)-1 ≡ 1 (mod p)
d) none of the mentioned

Answer: a
Clarification: According to Fermat’s little theorem ap-1 ≡ 1 (mod p).

4. 5 is quardratic non-residue of 7.
a) True
b) False

Answer: a
Clarification: Since there exists no number which gives 5 modulo 7 when squared.

5. 4 is quardratic residue of 7.
a) True
b) False

Answer: a
Clarification: Since 25 ≡ 4(mod)7, 4 is quardratic residue of 7.

6. 8 is quardratic residue of 17.
a) True
b) False

Answer: a
Clarification: Since 25 ≡ 8(mod)17.

7. 8 is quardratic residue of 11.
a) True
b) False

Answer: b
Clarification: Since x2 ≡ 8(mod)17 has no solutions.

8. Which of the following is a quardratic residue of 11?
a) 4
b) 5
c) 9
d) All of the mentioned

Answer: d
Clarification: Since 4, 16, 32 satisfies the criteria, all are quardratic residue of 11.

9. What is pseudo prime number?
a) is a probable prime and is not a prime number
b) is a prime number
c) does not share any property with prime number
d) none of the mentioned

Answer: a
Clarification: A pseudo prime number is an integer that shares a property common to all prime number and is not a prime number.

10. Pseudo prime are classified based on property which they satisfy, which of the following are classes of pseudoprimes?
a) Fermat pseudoprime
b) Fibonacci pseudoprime
c) Euler pseudoprime
d) All of the mentioned

Answer: d
Clarification: Fermat pseudoprime, Fibonacci pseudoprime, Euler pseudoprime are different classes of pseudoprimes.

250+ TOP MCQs on Counting – Pigeonhole Principle and Answers

Discrete Mathematics Multiple Choice Questions on “Counting – Pigeonhole Principle”.

1. A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out at random in the dark. How many socks must he take out to be sure that he has at least two blue socks?
a) 18
b) 35
c) 28
d) 14

Answer: d
Clarification: Given 12 red and 12 blue socks so, in order to take out at least 2 blue socks, first we need to take out 12 shocks (which might end up red in worst case) and then take out 2 socks (which would be definitely blue). Thus we need to take out total 14 socks.

2. The least number of computers required to connect 10 computers to 5 routers to guarantee 5 computers can directly access 5 routers is ______
a) 74
b) 104
c) 30
d) 67

Answer: c
Clarification: Since each 5 computer need directly connected with each router. So 25 connections + now remaining 5 computer, each connected to 5 different routers, so 5 connections = 30 connections. Hence,

c1->r1, r2, r3, r4, r5
c2->r1, r2, r3, r4, r5
c3->r1, r2, r3, r4, r5
c4->r1, r2, r3, r4, r5
c5->r1, r2, r3, r4, r5
c6->r1
c7->r2
c8->r3
c9->r4
c10->r5

Now, any pick of 5 computers will have a direct connection to all the 5 routers.

3. In a group of 267 people how many friends are there who have an identical number of friends in that group?
a) 266
b) 2
c) 138
d) 202

Answer: b
Clarification: Suppose each of the 267 members of the group has at least 1 friend. In this case, each of the 267 members of the group will have 1 to 267-1=266 friends. Now, consider the numbers from 1 to n-1 as holes and the n members as pigeons. Since there is n-1 holes and n pigeons there must exist a hole which must contain more than one pigeon. That means there must exist a number from 1 to n-1 which would contain more than 1 member. So, in a group of n members there must exist at least two persons having equal number of friends. A similar case occurs when there exist a person having no friends.

4. When four coins are tossed simultaneously, in _______ number of the outcomes at most two of the coins will turn up as heads.
a) 17
b) 28
c) 11
d) 43

Answer: c
Clarification: The question requires you to find number of the outcomes in which at most 2 coins turn up as heads i.e., 0 coins turn heads or 1 coin turns head or 2 coins turn heads. The number of outcomes in which 0 coins turn heads is 4C0 = 1 outcome. The number of outcomes in which 1 coin turns head is 4C1 = 6 outcomes. The number of outcomes in which 2 coins turn heads is,
4C2 = 15 outcomes. Therefore, total number of outcomes = 1 + 4 + 6 = 11 outcomes.

5. How many numbers must be selected from the set {1, 2, 3, 4} to guarantee that at least one pair of these numbers add up to 7?
a) 14
b) 5
c) 9
d) 24

Answer: b
Clarification: With 2 elements pairs which give sum as 7 = {(1,6), (2,5), (3,4), (4,3)}. So choosing 1 element from each group = 4 elements (in worst case 4 elements will be either {1,2,3,4} or {6,5,4,3}). Now using pigeonhole principle = we need to choose 1 more element so that sum will definitely be 7. So Number of elements must be 4 + 1 = 5.

6. During a month with 30 days, a cricket team plays at least one game a day, but no more than 45 games. There must be a period of some number of consecutive days during which the team must play exactly ______ number of games.
a) 17
b) 46
c) 124
d) 24

Answer: d
Clarification: Let a1 be the number of games played until day 1, and so on, ai be the no games played until i. Consider a sequence like a1,a2,…a30 where 1≤ai≤45, ∀ai. Add 14 to each element of the sequence we get a new sequence a1+14, a2+14, … a30+14 where, 15 ≤ ai+14 ≤ 59, ∀ai. Now we have two sequences 1. a1, a2, …, a30 and 2. a1+14, a2+14, …, a30+14. having 60 elements in total with each elements taking a value ≤ 59. So according to pigeon hole principle, there must be at least two elements taking the same value ≤59 i.e., ai = aj + 14 for some i and j. Therefore, there exists at least a period such as aj to ai, in which 14 matches are played.

7. In how many ways can 8 different dolls be packed in 5 identical gift boxes such that no box is empty if any of the boxes hold all of the toys?
a) 2351
b) 365
c) 2740
d) 1260

Answer: d
Clarification: Dolls are different but the boxes are identical. If none of the boxes is to remain empty, then we can pack the dolls in one of the following ways:
Case i. 2, 2, 2, 1, 1
Case ii. 3, 3, 1, 1
Case i: Number of ways of achieving the first option 2, 2, 2, 1, 1. Two dolls out of the 8 can be selected in 8C2 ways, another 2 out of the remaining 6 can be selected in 6C2 ways, another 2 out of the remaining 4 can be selected in 4C2 ways and the last two dolls can be selected in 1C1 ways each. However, as the boxes are identical, the two different ways of selecting which box holds the first two dolls and which one holds the second set of two dolls will look the same. Hence, we need to divide the result by 2. Therefore, total number of ways of achieving the 2, 2, 2, 1, 1 is = (8C2 * 6C2 * 4C2 * 1C1 * 1C1) / 2 = 1260.

8. A group of 20 girls plucked a total of 200 oranges. How many oranges can be plucked one of them?
a) 24
b) 10
c) 32
d) 7

Answer: a
Clarification: Suppose all of them plucked the different number of oranges. A girl can pluck at least 0 oranges and the number of oranges plucks by each student is distinct. So, total number of plucked oranges should be less than 100. But 0+1+2…..+19+20 = 210>200 a contradiction.
Thus there exist two girls who plucked the same number of oranges. If thus there exist two girls who plucked the same number of oranges. It means each girl of remaining 18 students plucked different number of oranges. Number of oranges Plucked by 18 students = 0+1+2+3…+17 = 153 oranges. Number of oranges plucked by remaining 2 student = 200 – 153 = 47. Both students plucked same number of oranges. So, Number of oranges plucked by one of them = 47/2=24.

9. In a get-together party, every person present shakes the hand of every other person. If there were 90 handshakes in all, how many persons were present at the party?
a) 15
b) 14
c) 16
d) 17

Answer: b
Clarification: Let the total number of persons present at the party be m, Then, [{x *(x−1)}/2] = 90.
x = 14.

10. A bag contains 25 balls such as 10 balls are red, 7 are white and 8 are blue. What is the minimum number of balls that must be picked up from the bag blindfolded (without replacing any of it) to be assured of picking at least one ball of each colour?
a) 10
b) 18
c) 63
d) 35

Answer: b
Clarification: Consider three buckets red, white and blue and we want the total number of balls such that each bucket contain at least one ball. Now consider the state of picking up a ball without replacement : (normally you consider the worst case scenario in these cases) Starting 10 balls all are red and thus goes to bucket name Red. Now again picking up the ball gives 7 balls which are of same colour and put all of them in a bucket named White. The next pick will definitely be of different colour thus: we picked 10 + 7 + 1 = 18.

250+ TOP MCQs on Discrete Probability – Bayes Theorem and Answers

Discrete Mathematics Multiple Choice Questions on “Discrete Probability – Bayes Theorem”.

1. A single card is drawn from a standard deck of playing cards. What is the probability that the card is a face card provided that a queen is drawn from the deck of cards?
a) (frac{3}{13})
b) (frac{1}{3})
c) (frac{4}{13})
d) (frac{1}{52})

Answer: b
Clarification: The probability that the card drawn is a queen = (frac{4}{52}), since there are 4 queens in a standard deck of 52 cards. If the event is “this card is a queen” the prior probability P(queen) = (frac{4}{52} = frac{1}{13}). The posterior probability P(queen|face) can be calculated using Bayes theorem: P(king|face) = P(face|king)/P(face)*P(king). Since every queen is also a face card, P(face|queen) = 1. The probability of a face card is P(face) = ((frac{3}{13})). [since there are 3 face cards in each suit (Jack, Queen, King)]. Using Bayes theorem gives P(queen|face) = (frac{13}{3}*frac{1}{13} = frac{1}{3}).

2. Naina receives emails that consists of 18% spam of those emails. The spam filter is 93% reliable i.e., 93% of the mails it marks as spam are actually a spam and 93% of spam mails are correctly labelled as spam. If a mail marked spam by her spam filter, determine the probability that it is really spam.
a) 50%
b) 84%
c) 39%
d) 63%

Answer: a
Clarification: 18% email are spam and 82% email are not spam. Now, 18% of mail marked as spam is spam and 82% mail marked as spam are not spam. By Bayes theorem the probability that a mail marked spam is really a spam = (Probability of being spam and being detected as spam)/(Probability of being detected as spam) = (0.18 * 0.82)/(0.18 * 0.82) + (0.18 * 0.82) = 0.5 or 50%.

3. A meeting has 12 employees. Given that 8 of the employees is a woman, find the probability that all the employees are women?
a) (frac{11}{23})
b) (frac{12}{35})
c) (frac{2}{9})
d) (frac{1}{8})

Answer: c
Clarification: Assume that the probability of an employee being a man or woman is ((frac{1}{2})). By using Bayes’ theorem: let B be the event that the meeting has 3 employees who is a woman and let A be the event that all employees are women. We want to find P(A|B) = (frac{P(B|A)*P(A)}{P(B)}). P(B|A) = 1, P(A) = (frac{1}{12}) and P(B) = (frac{8}{12}). So, P(A|B) = (frac{1*frac{1}{12}}{frac{8}{12}} = frac{1}{8}).

4. A cupboard A has 4 red carpets and 4 blue carpets and a cupboard B has 3 red carpets and 5 blue carpets. A carpet is selected from a cupboard and the carpet is chosen from the selected cupboard such that each carpet in the cupboard is equally likely to be chosen. Cupboards A and B can be selected in (frac{1}{5}) and (frac{3}{5}) ways respectively. Given that a carpet selected in the above process is a blue carpet, find the probability that it came from the cupboard B.
a) (frac{2}{5})
b) (frac{15}{19})
c) (frac{31}{73})
d) (frac{4}{9})

Answer: b
Clarification: The probability of selecting a blue carpet = (frac{1}{5} * frac{4}{8} + frac{3}{5} * frac{5}{8} = frac{4}{40} + frac{15}{40} = frac{19}{40}). Probability of selecting a blue carpet from cupboard, P(B) = (frac{3}{5} * frac{5}{8} = frac{15}{40}). Given that a carpet selected in the above process is a blue carpet, the probability that it came from the cupboard A is = (frac{frac{15}{40}}{frac{19}{40}} = frac{15}{19}).

5. Mangoes numbered 1 through 18 are placed in a bag for delivery. Two mangoes are drawn out of the bag without replacement. Find the probability such that all the mangoes have even numbers on them?
a) 43.7%
b) 34%
c) 6.8%
d) 9.3%

Answer: c
Clarification: The events are not independent. There will be a (frac{10}{18} = frac{5}{9}) chance that any of the mangoes in the bag is even. The probability that the first one is even is (frac{1}{2}), for the second mango, given that the first one was even, there are only 9 even numbered balls that could be drawn from a total of 17 balls, so the probability is (frac{9}{17}). For the third mango, since the first two are both odd, there are 8 even numbered mangoes that could be drawn from a total of 16 remaining balls and so the probability is (frac{8}{16}) and for fourth mango, the probability is = (frac{7}{15}). So the probability that all 4 mangoes are even numbered is (frac{10}{18}*frac{9}{17}*frac{8}{16}*frac{7}{16}) = 0.068 or 6.8%.

6. A family has two children. Given that one of the children is a girl and that she was born on a Monday, what is the probability that both children are girls?
a) (frac{13}{27})
b) (frac{23}{54})
c) (frac{12}{19})
d) (frac{43}{58})

Answer: a
Clarification: We let Y be the event that the family has one child who is a girl born on Tuesday and X be the event that both children are boys, and apply Bayes’ Theorem. Given that there are 7 days of the week and there are 49 possible combinations for the days of the week the two girls were born on and 13 of these have a girl who was born on a Monday, so P(Y|X) = (frac{13}{49}). P(X) remains unchanged at (frac{1}{4}). To calculate P(Y), there are 142 = 196 possible ways to select the gender and the day of the week the child was born on. There are 132 = 169 ways which do not have a girl born on Monday and which 196 – 169 = 27 which do, so P(Y) = (frac{27}{196}). This gives is that P(X|Y) = (frac{frac{13}{19}*frac{1}{4}}{frac{27}{196}} = frac{13}{27}).

7. Suppose a fair eight-sided die is rolled once. If the value on the die is 1, 3, 5 or 7 the die is rolled a second time. Determine the probability that the sum of values that turn up is at least 8?
a) (frac{32}{87})
b) (frac{12}{43})
c) (frac{6}{13})
d) (frac{23}{64})

Answer: d
Clarification: Sample space consists of 8*8=64 events. While (8) has (frac{1}{8}) probability of occurrence, (1,7) has only (frac{1}{64}) probability. So, the required probability = (frac{1}{6} + (9 * frac{1}{64}) = frac{69}{192} = frac{23}{64}).

8. A jar containing 8 marbles of which 4 red and 4 blue marbles are there. Find the probability of getting a red given the first one was red too.
a) (frac{4}{13})
b) (frac{2}{11})
c) (frac{3}{7})
d) (frac{8}{15})

Answer: c
Clarification: Suppose, P (A) = getting a red marble in the first turn, P (B) = getting a black marble in the second turn. P (A) = (frac{4}{8}) and P (B) = (frac{3}{7}) and P (A and B) = (frac{4}{8}*frac{3}{7} = frac{3}{14}) P(B/A) = (frac{P(A ,and ,B)}{P(A)} = frac{frac{3}{14}}{frac{1}{2}} = frac{3}{7}).

9. A bin contains 4 red and 6 blue balls and three balls are drawn at random. Find the probability such that both are of the same color.
a) (frac{10}{28})
b) (frac{1}{5})
c) (frac{1}{10})
d) (frac{4}{7})

Answer: b
Clarification: Total no of balls = 10. Number of ways drawing 3 balls at random out of 10 = 10C3 = 120. Probability of drawing 3 balls of same colour = 4C3 + 6C3 = 24. Hence, the required probability is (frac{24}{120} = frac{1}{5}).

10. A bucket contains 6 blue, 8 red and 9 black pens. If six pens are drawn one by one without replacement, find the probability of getting all black pens?
a) (frac{8}{213})
b) (frac{8}{4807})
c) (frac{5}{1204})
d) (frac{7}{4328})

Answer: b
Clarification: Total number of pens = 23, number of pens we have chosen = 6, total number of black pens = 9. According to the combination probability formula it states that nCr = (frac{n!}{r! (n-r)!}),
where n = total number of outcomes, r = random selection, P = (frac{^9C_6}{^{23}C_6} = frac{8}{4807}).

250+ TOP MCQs on Isomorphism in Graphs and Answers

Discrete Mathematics written test Questions & Answers on “Isomorphism in Graphs”.

1. A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or _______ modulo 4(for integral values of number of edges).
a) 6k, 6k-1
b) 4k, 4k+1
c) k, k+2
d) 2k+1, k

Answer: c
Clarification: By using invariant of isomorphism and property of edges of graph and its complement, we have: a) number of edges of isomorphic graphs must be the same.
b) number of edge of a graph + number of edges of complementary graph = Number of edges in Kn(complete graph), where n is the number of vertices in each of the 2 graphs which will be the same. So we know number of edges in Kn = n(n-1)/2. So number of edges of each of the above 2 graph(a graph and its complement) = n(n-1)/4. So this means the number of vertices in each of the 2 graphs should be of the form “4x” or “4x+1” for integral value of number of edges which is necessary. Hence the required answer is 4x or 4x+1 so that on doing modulo we get 0 which is the definition of congruence.

2. Every Isomorphic graph must have ________ representation.
a) cyclic
b) adjacency list
c) tree
d) adjacency matrix

Answer: d
Clarification: A graph can exist in different forms having the same number of vertices, edges and also the same edge connectivity, such graphs are called isomorphic graphs. Two graphs G1 and G2 are said to be isomorphic if −> 1) their number of components (vertices and edges) are same and 2) their edge connectivity is retained. Isomorphic graphs must have adjacency matrix representation.

3. A cycle on n vertices is isomorphic to its complement. What is the value of n?
a) 5
b) 32
c) 17
d) 8

Answer: a
Clarification: A cycle with n vertices has n edges. Number of edges in cycle = n and number of edges in its complement = (n*(n−1)/2) – n. To be isomorphism, both graphs should have equal number of edges. This gives, (n*(n-1)/2) – n = n
⇒ n = 5

4. How many perfect matchings are there in a complete graph of 10 vertices?
a) 60
b) 945
c) 756
d) 127

Answer: b
Clarification: Perfect matching is a set of edges such that each vertex appears only once and all vertices appear at least once (exactly one appearance). So for n vertices perfect matching will have n/2 edges and there won’t be any perfect matching if n is odd. For n=10, we can choose the first edge in 10C2 = 45 ways, second in 8C2=28 ways, third in 6C2=15 ways and so on. So, the total number of ways 45*28*15*6*1=113400. But perfect matching being a set, order of elements is not important and the permutations 5! of the 5 edges are same only. So, total number of perfect matching is 113400/5! = 945.

5. A graph G has the degree of each vertex is ≥ 3 say, deg(V) ≥ 3 ∀ V ∈ G such that 3|V| ≤ 2|E| and 3|R| ≤ 2|E|, then the graph is said to be ________ (R denotes region in the graph)
a) Planner graph
b) Polyhedral graph
c) Homomorphic graph
d) Isomorphic graph

Answer: b
Clarification: A simple connected planar graph is called a polyhedral graph if the degree of each vertex is(V) ≥ 3 such that deg(V) ≥ 3 ∀ V ∈ G and two conditions must satisfy i) 3|V| ≤ 2|E| and ii) 3|R| ≤ 2|E|.

6. A complete n-node graph Kn is planar if and only if _____________
a) n ≥ 6
b) n2 = n + 1
c) n ≤ 4
d) n + 3

Answer: c
Clarification: Any graph with 4 or less vertices is planar, any graph with 8 or less edges is planar and a complete n-node graph Kn is planar if and only if n ≤ 4.

7. A graph is ______ if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.
a) bipartite graph
b) planar graph
c) line graph
d) euler subgraph

Answer: b
Clarification: A graph is known as planar graph if and only if it does not contain a subgraph homeomorphic to k5 or k3,3.

8. An isomorphism of graphs G and H is a bijection f the vertex sets of G and H. Such that any two vertices u and v of G are adjacent in G if and only if ____________
a) f(u) and f(v) are contained in G but not contained in H
b) f(u) and f(v) are adjacent in H
c) f(u * v) = f(u) + f(v)
d) f(u) = f(u)2 + f(v)2

Answer: b
Clarification: Two graphs G and H are said to be isomorphic to each other if there exist a one to one correspondence, say f between the vertex sets V(G) and V(H) and a one to one correspondence g between the edge sets E(G) and E(H) with the following conditions:-
(i) for every vertex u in G, there exists a vertex u’ in H such that u’=f(u) and vice versa.
(ii) for every edge uv in G, g(uv)=f(u)*f(v)=u’v’ is H.

9. What is the grade of a planar graph consisting of 8 vertices and 15 edges?
a) 30
b) 15
c) 45
d) 106

Answer: a
Clarification: If G is a planar graph with n vertices and m edges then r(G) = 2m i.e. the grade or rank of G is equal to the twofold of the number of edges in G. So, the rank of the graph is 2*15=30 having 8 vertices and 15 edges.

10. A _______ is a graph with no homomorphism to any proper subgraph.
a) poset
b) core
c) walk
d) trail

Answer: b
Clarification: A core can be defined as a graph that does not retract to any proper subgraph. Every graph G is homomorphically equivalent to a unique core called the core of G.