Combinatorics and Graph Theory — 200 Discrete Mathematics MCQs
200 practice MCQs based on the supplied Discrete Mathematics course outline. Each question has four options and an expandable answer with an explanation. This is an original practice bank, not a copy of the recommended textbooks.
Counting Methods
Q1. How many ways can 3 distinct books be arranged on one shelf?
- A. 6
- B. 2
- C. 18
- D. 9
Show correct answer and explanation
Correct answer: A. 6
There are 3! permutations of 3 distinct objects.
Q2. A student chooses one of 3 shirts and one of 4 pairs of trousers. How many outfits are possible?
- A. 8
- B. 12
- C. 7
- D. 11
Show correct answer and explanation
Correct answer: B. 12
By the product rule: 3×4=12.
Q3. A menu offers 3 desserts or 5 drinks as a single choice (disjoint options). How many choices?
- A. 8
- B. 15
- C. 7
- D. 16
Show correct answer and explanation
Correct answer: A. 8
By the addition rule: 3+5=8.
Q4. How many ways can 4 distinct books be arranged on one shelf?
- A. 6
- B. 96
- C. 16
- D. 24
Show correct answer and explanation
Correct answer: D. 24
There are 4! permutations of 4 distinct objects.
Q5. A student chooses one of 4 shirts and one of 5 pairs of trousers. How many outfits are possible?
- A. 20
- B. 9
- C. 19
- D. 10
Show correct answer and explanation
Correct answer: A. 20
By the product rule: 4×5=20.
Q6. A menu offers 4 desserts or 6 drinks as a single choice (disjoint options). How many choices?
- A. 24
- B. 9
- C. 25
- D. 10
Show correct answer and explanation
Correct answer: D. 10
By the addition rule: 4+6=10.
Q7. How many ways can 5 distinct books be arranged on one shelf?
- A. 600
- B. 25
- C. 120
- D. 24
Show correct answer and explanation
Correct answer: C. 120
There are 5! permutations of 5 distinct objects.
Q8. A student chooses one of 5 shirts and one of 6 pairs of trousers. How many outfits are possible?
- A. 11
- B. 29
- C. 12
- D. 30
Show correct answer and explanation
Correct answer: D. 30
By the product rule: 5×6=30.
Q9. A menu offers 5 desserts or 7 drinks as a single choice (disjoint options). How many choices?
- A. 11
- B. 36
- C. 12
- D. 35
Show correct answer and explanation
Correct answer: C. 12
By the addition rule: 5+7=12.
Q10. How many ways can 6 distinct books be arranged on one shelf?
- A. 36
- B. 720
- C. 120
- D. 4320
Show correct answer and explanation
Correct answer: B. 720
There are 6! permutations of 6 distinct objects.
Q11. A student chooses one of 6 shirts and one of 7 pairs of trousers. How many outfits are possible?
- A. 41
- B. 14
- C. 42
- D. 13
Show correct answer and explanation
Correct answer: C. 42
By the product rule: 6×7=42.
Q12. A menu offers 6 desserts or 8 drinks as a single choice (disjoint options). How many choices?
- A. 49
- B. 14
- C. 48
- D. 13
Show correct answer and explanation
Correct answer: B. 14
By the addition rule: 6+8=14.
Q13. How many ways can 7 distinct books be arranged on one shelf?
- A. 5040
- B. 720
- C. 35280
- D. 49
Show correct answer and explanation
Correct answer: A. 5040
There are 7! permutations of 7 distinct objects.
Q14. A student chooses one of 7 shirts and one of 8 pairs of trousers. How many outfits are possible?
- A. 16
- B. 56
- C. 15
- D. 55
Show correct answer and explanation
Correct answer: B. 56
By the product rule: 7×8=56.
Q15. A menu offers 7 desserts or 9 drinks as a single choice (disjoint options). How many choices?
- A. 16
- B. 63
- C. 15
- D. 64
Show correct answer and explanation
Correct answer: A. 16
By the addition rule: 7+9=16.
Q16. How many ways can 8 distinct books be arranged on one shelf?
- A. 5040
- B. 322560
- C. 64
- D. 40320
Show correct answer and explanation
Correct answer: D. 40320
There are 8! permutations of 8 distinct objects.
Q17. A student chooses one of 8 shirts and one of 9 pairs of trousers. How many outfits are possible?
- A. 72
- B. 17
- C. 71
- D. 18
Show correct answer and explanation
Correct answer: A. 72
By the product rule: 8×9=72.
Q18. A menu offers 8 desserts or 10 drinks as a single choice (disjoint options). How many choices?
- A. 80
- B. 17
- C. 81
- D. 18
Show correct answer and explanation
Correct answer: D. 18
By the addition rule: 8+10=18.
Q19. How many ways can 9 distinct books be arranged on one shelf?
- A. 3265920
- B. 81
- C. 362880
- D. 40320
Show correct answer and explanation
Correct answer: C. 362880
There are 9! permutations of 9 distinct objects.
Q20. A student chooses one of 9 shirts and one of 10 pairs of trousers. How many outfits are possible?
- A. 19
- B. 89
- C. 20
- D. 90
Show correct answer and explanation
Correct answer: D. 90
By the product rule: 9×10=90.
Q21. A menu offers 9 desserts or 11 drinks as a single choice (disjoint options). How many choices?
- A. 19
- B. 100
- C. 20
- D. 99
Show correct answer and explanation
Correct answer: C. 20
By the addition rule: 9+11=20.
Q22. How many ways can 10 distinct books be arranged on one shelf?
- A. 100
- B. 3628800
- C. 362880
- D. 36288000
Show correct answer and explanation
Correct answer: B. 3628800
There are 10! permutations of 10 distinct objects.
Q23. A student chooses one of 10 shirts and one of 11 pairs of trousers. How many outfits are possible?
- A. 109
- B. 22
- C. 110
- D. 21
Show correct answer and explanation
Correct answer: C. 110
By the product rule: 10×11=110.
Q24. A menu offers 10 desserts or 12 drinks as a single choice (disjoint options). How many choices?
- A. 121
- B. 22
- C. 120
- D. 21
Show correct answer and explanation
Correct answer: B. 22
By the addition rule: 10+12=22.
Permutations
Q25. How many ordered selections of 2 objects can be made from 6 distinct objects without replacement?
- A. 12
- B. 15
- C. 36
- D. 30
Show correct answer and explanation
Correct answer: D. 30
P(6,2) = 6!/(6−2)! = 30.
Q26. How many ordered selections of 3 objects can be made from 7 distinct objects without replacement?
- A. 70
- B. 343
- C. 210
- D. 21
Show correct answer and explanation
Correct answer: C. 210
P(7,3) = 7!/(7−3)! = 210.
Q27. How many ordered selections of 4 objects can be made from 8 distinct objects without replacement?
- A. 4096
- B. 1680
- C. 32
- D. 420
Show correct answer and explanation
Correct answer: B. 1680
P(8,4) = 8!/(8−4)! = 1680.
Q28. How many ordered selections of 2 objects can be made from 9 distinct objects without replacement?
- A. 72
- B. 18
- C. 36
- D. 81
Show correct answer and explanation
Correct answer: A. 72
P(9,2) = 9!/(9−2)! = 72.
Q29. How many ordered selections of 3 objects can be made from 10 distinct objects without replacement?
- A. 30
- B. 240
- C. 1000
- D. 720
Show correct answer and explanation
Correct answer: D. 720
P(10,3) = 10!/(10−3)! = 720.
Q30. How many ordered selections of 4 objects can be made from 11 distinct objects without replacement?
- A. 1980
- B. 14641
- C. 7920
- D. 44
Show correct answer and explanation
Correct answer: C. 7920
P(11,4) = 11!/(11−4)! = 7920.
Q31. How many ordered selections of 2 objects can be made from 12 distinct objects without replacement?
- A. 144
- B. 132
- C. 24
- D. 66
Show correct answer and explanation
Correct answer: B. 132
P(12,2) = 12!/(12−2)! = 132.
Q32. How many ordered selections of 3 objects can be made from 13 distinct objects without replacement?
- A. 1716
- B. 39
- C. 572
- D. 2197
Show correct answer and explanation
Correct answer: A. 1716
P(13,3) = 13!/(13−3)! = 1716.
Combinations
Q33. How many 2-element subsets can be selected from 7 distinct elements?
- A. 14
- B. 49
- C. 21
- D. 42
Show correct answer and explanation
Correct answer: C. 21
C(7,2) = 7!/[2!(7−2)!] = 21.
Q34. How many 3-element subsets can be selected from 8 distinct elements?
- A. 512
- B. 56
- C. 168
- D. 24
Show correct answer and explanation
Correct answer: B. 56
C(8,3) = 8!/[3!(8−3)!] = 56.
Q35. How many 4-element subsets can be selected from 9 distinct elements?
- A. 126
- B. 504
- C. 36
- D. 6561
Show correct answer and explanation
Correct answer: A. 126
C(9,4) = 9!/[4!(9−4)!] = 126.
Q36. How many 2-element subsets can be selected from 10 distinct elements?
- A. 90
- B. 20
- C. 100
- D. 45
Show correct answer and explanation
Correct answer: D. 45
C(10,2) = 10!/[2!(10−2)!] = 45.
Q37. How many 3-element subsets can be selected from 11 distinct elements?
- A. 33
- B. 1331
- C. 165
- D. 495
Show correct answer and explanation
Correct answer: C. 165
C(11,3) = 11!/[3!(11−3)!] = 165.
Q38. How many 4-element subsets can be selected from 12 distinct elements?
- A. 20736
- B. 495
- C. 1980
- D. 48
Show correct answer and explanation
Correct answer: B. 495
C(12,4) = 12!/[4!(12−4)!] = 495.
Q39. How many 2-element subsets can be selected from 13 distinct elements?
- A. 78
- B. 156
- C. 26
- D. 169
Show correct answer and explanation
Correct answer: A. 78
C(13,2) = 13!/[2!(13−2)!] = 78.
Q40. How many 3-element subsets can be selected from 14 distinct elements?
- A. 1092
- B. 42
- C. 2744
- D. 364
Show correct answer and explanation
Correct answer: D. 364
C(14,3) = 14!/[3!(14−3)!] = 364.
Counting With Repetition
Q41. How many length-2 sequences can be formed from 3 symbols if repetition is allowed?
- A. 6
- B. 8
- C. 3
- D. 9
Show correct answer and explanation
Correct answer: D. 9
Each of the 2 positions has 3 choices, giving 3^2=9.
Q42. How many length-3 sequences can be formed from 4 symbols if repetition is allowed?
- A. 63
- B. 16
- C. 64
- D. 12
Show correct answer and explanation
Correct answer: C. 64
Each of the 3 positions has 4 choices, giving 4^3=64.
Q43. How many length-4 sequences can be formed from 5 symbols if repetition is allowed?
- A. 125
- B. 625
- C. 20
- D. 624
Show correct answer and explanation
Correct answer: B. 625
Each of the 4 positions has 5 choices, giving 5^4=625.
Q44. How many length-2 sequences can be formed from 6 symbols if repetition is allowed?
- A. 36
- B. 12
- C. 35
- D. 6
Show correct answer and explanation
Correct answer: A. 36
Each of the 2 positions has 6 choices, giving 6^2=36.
Q45. How many length-3 sequences can be formed from 7 symbols if repetition is allowed?
- A. 21
- B. 342
- C. 49
- D. 343
Show correct answer and explanation
Correct answer: D. 343
Each of the 3 positions has 7 choices, giving 7^3=343.
Q46. How many length-4 sequences can be formed from 8 symbols if repetition is allowed?
- A. 4095
- B. 512
- C. 4096
- D. 32
Show correct answer and explanation
Correct answer: C. 4096
Each of the 4 positions has 8 choices, giving 8^4=4096.
Q47. How many length-2 sequences can be formed from 9 symbols if repetition is allowed?
- A. 9
- B. 81
- C. 18
- D. 80
Show correct answer and explanation
Correct answer: B. 81
Each of the 2 positions has 9 choices, giving 9^2=81.
Q48. How many length-3 sequences can be formed from 10 symbols if repetition is allowed?
- A. 1000
- B. 30
- C. 999
- D. 100
Show correct answer and explanation
Correct answer: A. 1000
Each of the 3 positions has 10 choices, giving 10^3=1000.
Pigeonhole Principle
Q49. If 4 objects are placed into 3 boxes, at least how many objects must share a box?
- A. 3
- B. 4
- C. 2
- D. 1
Show correct answer and explanation
Correct answer: C. 2
Since 4>3, some box contains at least two objects.
Q50. If 5 objects are distributed among 2 boxes, what minimum occupancy is guaranteed in some box?
- A. 4
- B. 3
- C. 1
- D. 2
Show correct answer and explanation
Correct answer: B. 3
Ceiling(5/2) = 3, so some box has at least three objects.
Q51. If 5 objects are placed into 4 boxes, at least how many objects must share a box?
- A. 4
- B. 2
- C. 1
- D. 3
Show correct answer and explanation
Correct answer: B. 2
Since 5>4, some box contains at least two objects.
Q52. If 7 objects are distributed among 3 boxes, what minimum occupancy is guaranteed in some box?
- A. 3
- B. 1
- C. 2
- D. 4
Show correct answer and explanation
Correct answer: A. 3
Ceiling(7/3) = 3, so some box has at least three objects.
Q53. If 6 objects are placed into 5 boxes, at least how many objects must share a box?
- A. 2
- B. 1
- C. 3
- D. 5
Show correct answer and explanation
Correct answer: A. 2
Since 6>5, some box contains at least two objects.
Q54. If 9 objects are distributed among 4 boxes, what minimum occupancy is guaranteed in some box?
- A. 1
- B. 2
- C. 4
- D. 3
Show correct answer and explanation
Correct answer: D. 3
Ceiling(9/4) = 3, so some box has at least three objects.
Q55. If 7 objects are placed into 6 boxes, at least how many objects must share a box?
- A. 1
- B. 3
- C. 6
- D. 2
Show correct answer and explanation
Correct answer: D. 2
Since 7>6, some box contains at least two objects.
Q56. If 11 objects are distributed among 5 boxes, what minimum occupancy is guaranteed in some box?
- A. 2
- B. 4
- C. 3
- D. 1
Show correct answer and explanation
Correct answer: C. 3
Ceiling(11/5) = 3, so some box has at least three objects.
Q57. If 8 objects are placed into 7 boxes, at least how many objects must share a box?
- A. 3
- B. 7
- C. 2
- D. 1
Show correct answer and explanation
Correct answer: C. 2
Since 8>7, some box contains at least two objects.
Q58. If 13 objects are distributed among 6 boxes, what minimum occupancy is guaranteed in some box?
- A. 4
- B. 3
- C. 1
- D. 2
Show correct answer and explanation
Correct answer: B. 3
Ceiling(13/6) = 3, so some box has at least three objects.
Q59. If 9 objects are placed into 8 boxes, at least how many objects must share a box?
- A. 8
- B. 2
- C. 1
- D. 3
Show correct answer and explanation
Correct answer: B. 2
Since 9>8, some box contains at least two objects.
Q60. If 15 objects are distributed among 7 boxes, what minimum occupancy is guaranteed in some box?
- A. 3
- B. 1
- C. 2
- D. 4
Show correct answer and explanation
Correct answer: A. 3
Ceiling(15/7) = 3, so some box has at least three objects.
Q61. If 10 objects are placed into 9 boxes, at least how many objects must share a box?
- A. 2
- B. 1
- C. 3
- D. 9
Show correct answer and explanation
Correct answer: A. 2
Since 10>9, some box contains at least two objects.
Q62. If 17 objects are distributed among 8 boxes, what minimum occupancy is guaranteed in some box?
- A. 1
- B. 2
- C. 4
- D. 3
Show correct answer and explanation
Correct answer: D. 3
Ceiling(17/8) = 3, so some box has at least three objects.
Q63. If 11 objects are placed into 10 boxes, at least how many objects must share a box?
- A. 1
- B. 3
- C. 10
- D. 2
Show correct answer and explanation
Correct answer: D. 2
Since 11>10, some box contains at least two objects.
Q64. If 19 objects are distributed among 9 boxes, what minimum occupancy is guaranteed in some box?
- A. 2
- B. 4
- C. 3
- D. 1
Show correct answer and explanation
Correct answer: C. 3
Ceiling(19/9) = 3, so some box has at least three objects.
Graphs & Types
Q65. How many edges are in the complete graph K4?
- A. 6
- B. 4
- C. 3
- D. 12
Show correct answer and explanation
Correct answer: A. 6
Every unordered pair of vertices forms an edge: 4(4−1)/2.
Q66. How many edges does a simple cycle graph C4 have?
- A. 3
- B. 5
- C. 6
- D. 4
Show correct answer and explanation
Correct answer: D. 4
A cycle has one edge for each of its 4 vertices.
Q67. How many edges are in the path graph P4 with 4 vertices?
- A. 5
- B. 8
- C. 3
- D. 4
Show correct answer and explanation
Correct answer: C. 3
A path through 4 vertices uses 4−1 edges.
Q68. How many edges are in the complete graph K5?
- A. 5
- B. 4
- C. 20
- D. 10
Show correct answer and explanation
Correct answer: D. 10
Every unordered pair of vertices forms an edge: 5(5−1)/2.
Q69. How many edges does a simple cycle graph C5 have?
- A. 6
- B. 10
- C. 5
- D. 4
Show correct answer and explanation
Correct answer: C. 5
A cycle has one edge for each of its 5 vertices.
Q70. How many edges are in the path graph P5 with 5 vertices?
- A. 10
- B. 4
- C. 5
- D. 6
Show correct answer and explanation
Correct answer: B. 4
A path through 5 vertices uses 5−1 edges.
Q71. How many edges are in the complete graph K6?
- A. 5
- B. 30
- C. 15
- D. 6
Show correct answer and explanation
Correct answer: C. 15
Every unordered pair of vertices forms an edge: 6(6−1)/2.
Q72. How many edges does a simple cycle graph C6 have?
- A. 15
- B. 6
- C. 5
- D. 7
Show correct answer and explanation
Correct answer: B. 6
A cycle has one edge for each of its 6 vertices.
Q73. How many edges are in the path graph P6 with 6 vertices?
- A. 5
- B. 6
- C. 7
- D. 12
Show correct answer and explanation
Correct answer: A. 5
A path through 6 vertices uses 6−1 edges.
Q74. How many edges are in the complete graph K7?
- A. 42
- B. 21
- C. 7
- D. 6
Show correct answer and explanation
Correct answer: B. 21
Every unordered pair of vertices forms an edge: 7(7−1)/2.
Q75. How many edges does a simple cycle graph C7 have?
- A. 7
- B. 6
- C. 8
- D. 21
Show correct answer and explanation
Correct answer: A. 7
A cycle has one edge for each of its 7 vertices.
Q76. How many edges are in the path graph P7 with 7 vertices?
- A. 7
- B. 8
- C. 14
- D. 6
Show correct answer and explanation
Correct answer: D. 6
A path through 7 vertices uses 7−1 edges.
Q77. How many edges are in the complete graph K8?
- A. 28
- B. 8
- C. 7
- D. 56
Show correct answer and explanation
Correct answer: A. 28
Every unordered pair of vertices forms an edge: 8(8−1)/2.
Q78. How many edges does a simple cycle graph C8 have?
- A. 7
- B. 9
- C. 28
- D. 8
Show correct answer and explanation
Correct answer: D. 8
A cycle has one edge for each of its 8 vertices.
Q79. How many edges are in the path graph P8 with 8 vertices?
- A. 9
- B. 16
- C. 7
- D. 8
Show correct answer and explanation
Correct answer: C. 7
A path through 8 vertices uses 8−1 edges.
Q80. How many edges are in the complete graph K9?
- A. 9
- B. 8
- C. 72
- D. 36
Show correct answer and explanation
Correct answer: D. 36
Every unordered pair of vertices forms an edge: 9(9−1)/2.
Q81. How many edges does a simple cycle graph C9 have?
- A. 10
- B. 36
- C. 9
- D. 8
Show correct answer and explanation
Correct answer: C. 9
A cycle has one edge for each of its 9 vertices.
Q82. How many edges are in the path graph P9 with 9 vertices?
- A. 18
- B. 8
- C. 9
- D. 10
Show correct answer and explanation
Correct answer: B. 8
A path through 9 vertices uses 9−1 edges.
Q83. How many edges are in the complete graph K10?
- A. 9
- B. 90
- C. 45
- D. 10
Show correct answer and explanation
Correct answer: C. 45
Every unordered pair of vertices forms an edge: 10(10−1)/2.
Q84. How many edges does a simple cycle graph C10 have?
- A. 45
- B. 10
- C. 9
- D. 11
Show correct answer and explanation
Correct answer: B. 10
A cycle has one edge for each of its 10 vertices.
Q85. How many edges are in the path graph P10 with 10 vertices?
- A. 9
- B. 10
- C. 11
- D. 20
Show correct answer and explanation
Correct answer: A. 9
A path through 10 vertices uses 10−1 edges.
Q86. How many edges are in the complete graph K11?
- A. 110
- B. 55
- C. 11
- D. 10
Show correct answer and explanation
Correct answer: B. 55
Every unordered pair of vertices forms an edge: 11(11−1)/2.
Q87. How many edges does a simple cycle graph C11 have?
- A. 11
- B. 10
- C. 12
- D. 55
Show correct answer and explanation
Correct answer: A. 11
A cycle has one edge for each of its 11 vertices.
Q88. How many edges are in the path graph P11 with 11 vertices?
- A. 11
- B. 12
- C. 22
- D. 10
Show correct answer and explanation
Correct answer: D. 10
A path through 11 vertices uses 11−1 edges.
Trees & Spanning Trees
Q89. A tree has 5 vertices. How many edges does it have?
- A. 8
- B. 4
- C. 5
- D. 6
Show correct answer and explanation
Correct answer: B. 4
Every finite tree has exactly |V|−1 edges.
Q90. How many leaves does the star graph K₁,4 have?
- A. 4
- B. 3
- C. 5
- D. 1
Show correct answer and explanation
Correct answer: A. 4
All 4 outer vertices have degree one.
Q91. A tree has 6 vertices. How many edges does it have?
- A. 5
- B. 6
- C. 7
- D. 10
Show correct answer and explanation
Correct answer: A. 5
Every finite tree has exactly |V|−1 edges.
Q92. How many leaves does the star graph K₁,5 have?
- A. 4
- B. 6
- C. 1
- D. 5
Show correct answer and explanation
Correct answer: D. 5
All 5 outer vertices have degree one.
Q93. A tree has 7 vertices. How many edges does it have?
- A. 7
- B. 8
- C. 12
- D. 6
Show correct answer and explanation
Correct answer: D. 6
Every finite tree has exactly |V|−1 edges.
Q94. How many leaves does the star graph K₁,6 have?
- A. 7
- B. 1
- C. 6
- D. 5
Show correct answer and explanation
Correct answer: C. 6
All 6 outer vertices have degree one.
Q95. A tree has 8 vertices. How many edges does it have?
- A. 9
- B. 14
- C. 7
- D. 8
Show correct answer and explanation
Correct answer: C. 7
Every finite tree has exactly |V|−1 edges.
Q96. How many leaves does the star graph K₁,7 have?
- A. 1
- B. 7
- C. 6
- D. 8
Show correct answer and explanation
Correct answer: B. 7
All 7 outer vertices have degree one.
Q97. A tree has 9 vertices. How many edges does it have?
- A. 16
- B. 8
- C. 9
- D. 10
Show correct answer and explanation
Correct answer: B. 8
Every finite tree has exactly |V|−1 edges.
Q98. How many leaves does the star graph K₁,8 have?
- A. 8
- B. 7
- C. 9
- D. 1
Show correct answer and explanation
Correct answer: A. 8
All 8 outer vertices have degree one.
Q99. A tree has 10 vertices. How many edges does it have?
- A. 9
- B. 10
- C. 11
- D. 18
Show correct answer and explanation
Correct answer: A. 9
Every finite tree has exactly |V|−1 edges.
Q100. How many leaves does the star graph K₁,9 have?
- A. 8
- B. 10
- C. 1
- D. 9
Show correct answer and explanation
Correct answer: D. 9
All 9 outer vertices have degree one.
Q101. A tree has 11 vertices. How many edges does it have?
- A. 11
- B. 12
- C. 20
- D. 10
Show correct answer and explanation
Correct answer: D. 10
Every finite tree has exactly |V|−1 edges.
Q102. How many leaves does the star graph K₁,10 have?
- A. 11
- B. 1
- C. 10
- D. 9
Show correct answer and explanation
Correct answer: C. 10
All 10 outer vertices have degree one.
Q103. A tree has 12 vertices. How many edges does it have?
- A. 13
- B. 22
- C. 11
- D. 12
Show correct answer and explanation
Correct answer: C. 11
Every finite tree has exactly |V|−1 edges.
Q104. How many leaves does the star graph K₁,11 have?
- A. 1
- B. 11
- C. 10
- D. 12
Show correct answer and explanation
Correct answer: B. 11
All 11 outer vertices have degree one.
Graphs & Degree
Q105. In the complete graph K4, what is the degree of each vertex?
- A. 4
- B. 2
- C. 8
- D. 3
Show correct answer and explanation
Correct answer: D. 3
Each vertex is adjacent to the other 4−1 vertices.
Q106. An undirected graph has 6 edges. What is the sum of all vertex degrees?
- A. 13
- B. 36
- C. 12
- D. 6
Show correct answer and explanation
Correct answer: C. 12
By the handshaking lemma, the sum of degrees is 2|E|=12.
Q107. In the complete graph K5, what is the degree of each vertex?
- A. 3
- B. 10
- C. 4
- D. 5
Show correct answer and explanation
Correct answer: C. 4
Each vertex is adjacent to the other 5−1 vertices.
Q108. An undirected graph has 7 edges. What is the sum of all vertex degrees?
- A. 49
- B. 14
- C. 7
- D. 15
Show correct answer and explanation
Correct answer: B. 14
By the handshaking lemma, the sum of degrees is 2|E|=14.
Q109. In the complete graph K6, what is the degree of each vertex?
- A. 12
- B. 5
- C. 6
- D. 4
Show correct answer and explanation
Correct answer: B. 5
Each vertex is adjacent to the other 6−1 vertices.
Q110. An undirected graph has 8 edges. What is the sum of all vertex degrees?
- A. 16
- B. 8
- C. 17
- D. 64
Show correct answer and explanation
Correct answer: A. 16
By the handshaking lemma, the sum of degrees is 2|E|=16.
Q111. In the complete graph K7, what is the degree of each vertex?
- A. 6
- B. 7
- C. 5
- D. 14
Show correct answer and explanation
Correct answer: A. 6
Each vertex is adjacent to the other 7−1 vertices.
Q112. An undirected graph has 9 edges. What is the sum of all vertex degrees?
- A. 9
- B. 19
- C. 81
- D. 18
Show correct answer and explanation
Correct answer: D. 18
By the handshaking lemma, the sum of degrees is 2|E|=18.
Q113. In the complete graph K8, what is the degree of each vertex?
- A. 8
- B. 6
- C. 16
- D. 7
Show correct answer and explanation
Correct answer: D. 7
Each vertex is adjacent to the other 8−1 vertices.
Q114. An undirected graph has 10 edges. What is the sum of all vertex degrees?
- A. 21
- B. 100
- C. 20
- D. 10
Show correct answer and explanation
Correct answer: C. 20
By the handshaking lemma, the sum of degrees is 2|E|=20.
Q115. In the complete graph K9, what is the degree of each vertex?
- A. 7
- B. 18
- C. 8
- D. 9
Show correct answer and explanation
Correct answer: C. 8
Each vertex is adjacent to the other 9−1 vertices.
Q116. An undirected graph has 11 edges. What is the sum of all vertex degrees?
- A. 121
- B. 22
- C. 11
- D. 23
Show correct answer and explanation
Correct answer: B. 22
By the handshaking lemma, the sum of degrees is 2|E|=22.
Q117. In the complete graph K10, what is the degree of each vertex?
- A. 20
- B. 9
- C. 10
- D. 8
Show correct answer and explanation
Correct answer: B. 9
Each vertex is adjacent to the other 10−1 vertices.
Q118. An undirected graph has 12 edges. What is the sum of all vertex degrees?
- A. 24
- B. 12
- C. 25
- D. 144
Show correct answer and explanation
Correct answer: A. 24
By the handshaking lemma, the sum of degrees is 2|E|=24.
Q119. In the complete graph K11, what is the degree of each vertex?
- A. 10
- B. 11
- C. 9
- D. 22
Show correct answer and explanation
Correct answer: A. 10
Each vertex is adjacent to the other 11−1 vertices.
Q120. An undirected graph has 13 edges. What is the sum of all vertex degrees?
- A. 13
- B. 27
- C. 169
- D. 26
Show correct answer and explanation
Correct answer: D. 26
By the handshaking lemma, the sum of degrees is 2|E|=26.
Eulerian & Hamiltonian Paths
Q121. A connected graph with exactly two odd-degree vertices (case 1) has which property?
- A. It must be a complete graph.
- B. It has an Euler trail but no Euler circuit.
- C. It has an Euler circuit.
- D. It has no Euler trail.
Show correct answer and explanation
Correct answer: B. It has an Euler trail but no Euler circuit.
A connected graph has an Euler trail with different endpoints iff exactly two vertices have odd degree.
Q122. A connected graph has all vertices of even degree. What Eulerian feature does it have?
- A. An Euler circuit
- B. Exactly two odd-degree vertices
- C. No closed trail
- D. No edges
Show correct answer and explanation
Correct answer: A. An Euler circuit
A connected graph with all even vertex degrees has an Euler circuit.
Q123. How many odd-degree vertices may a finite undirected graph have?
- A. Any odd number
- B. Only one
- C. An even number
- D. Exactly three
Show correct answer and explanation
Correct answer: C. An even number
The handshaking lemma implies that the number of odd-degree vertices is even.
Q124. Which graph has an Euler circuit?
- A. A path with 4 vertices
- B. A cycle C5
- C. A star K₁,3
- D. A tree with 5 vertices
Show correct answer and explanation
Correct answer: B. A cycle C5
Every vertex of the cycle C5 has degree 2 and the graph is connected.
Q125. Does the path graph P5 have an Euler trail?
- A. Yes, but no Euler circuit
- B. Yes, with an Euler circuit
- C. No, it has four odd vertices
- D. Only if another edge is added
Show correct answer and explanation
Correct answer: A. Yes, but no Euler circuit
A nontrivial path has exactly two degree-one vertices and all other degrees equal 2.
Q126. Can a connected graph with four odd-degree vertices have an Euler trail that uses each edge once?
- A. Yes, always
- B. Only when it is complete
- C. No
- D. Only when it is planar
Show correct answer and explanation
Correct answer: C. No
An Euler trail in a connected graph requires exactly zero or two odd-degree vertices.
Q127. A simple cycle C6 has how many odd-degree vertices?
- A. 2
- B. 6
- C. 1
- D. 0
Show correct answer and explanation
Correct answer: D. 0
All six vertices have degree 2, so none has odd degree.
Q128. For a connected graph with exactly two odd vertices u and v, where must an Euler trail start and end?
- A. At the same vertex
- B. At u and v in either order
- C. At any two even vertices
- D. At vertices of highest degree
Show correct answer and explanation
Correct answer: B. At u and v in either order
In an open Euler trail the endpoints are exactly the odd-degree vertices.
Graph Isomorphism
Q129. Which property must be identical in two isomorphic simple graphs (case 1)?
- A. Their sorted vertex-degree sequences
- B. Their vertex labels
- C. Their drawing coordinates
- D. Their vertex names
Show correct answer and explanation
Correct answer: A. Their sorted vertex-degree sequences
Graph isomorphisms preserve adjacency and thus every vertex degree.
Q130. Two isomorphic simple graphs must have the same number of what?
- A. Vertex names
- B. Vertices and edges
- C. Drawing crossings
- D. Vertex labels
Show correct answer and explanation
Correct answer: B. Vertices and edges
An isomorphism is a bijection on vertices that preserves adjacency and thus the edge count.
Q131. If one simple graph contains a triangle and another has no triangles, can they be isomorphic?
- A. Yes, always
- B. Only if both are trees
- C. No
- D. Only if their degrees match
Show correct answer and explanation
Correct answer: C. No
Graph isomorphisms preserve cycles of length three.
Q132. Can two graphs with different numbers of connected components be isomorphic?
- A. No
- B. Yes, if both are planar
- C. Yes, if edge counts match
- D. Yes, after relabelling
Show correct answer and explanation
Correct answer: A. No
An isomorphism preserves connectedness and the number of connected components.
Q133. Which pair of graphs is isomorphic?
- A. P4 and C4
- B. K3 and P3
- C. C4 and K4
- D. Two copies of P5 with different vertex labels
Show correct answer and explanation
Correct answer: D. Two copies of P5 with different vertex labels
Changing vertex labels does not alter the graph’s adjacency structure.
Q134. Is having the same sorted degree sequence sufficient to guarantee that two simple graphs are isomorphic?
- A. Yes, always
- B. No, not in general
- C. Only if both have an even number of vertices
- D. Only for directed graphs
Show correct answer and explanation
Correct answer: B. No, not in general
Nonisomorphic graphs can have identical sorted degree sequences.
Q135. If G is isomorphic to a tree T, which statement must hold?
- A. G is also a tree
- B. G must be complete
- C. G must have a cycle
- D. G has no vertices
Show correct answer and explanation
Correct answer: A. G is also a tree
Graph isomorphisms preserve connectedness and the absence of cycles.
Q136. If two graphs are isomorphic, what happens to vertex adjacency?
- A. It is always reversed
- B. It disappears
- C. It is preserved under a bijection
- D. It depends on drawing coordinates
Show correct answer and explanation
Correct answer: C. It is preserved under a bijection
The defining bijection of an isomorphism preserves adjacency.
Shortest Path
Q137. A weighted graph has edges A–B of weight 2, B–C of weight 3, and A–C of weight 8. What is the shortest A-to-C distance?
- A. 8
- B. 6
- C. 13
- D. 5
Show correct answer and explanation
Correct answer: D. 5
Compare the direct route (8) with A–B–C (2+3=5); choose the smaller.
Q138. A weighted graph has edges A–B of weight 3, B–C of weight 4, and A–C of weight 9. What is the shortest A-to-C distance?
- A. 8
- B. 16
- C. 7
- D. 9
Show correct answer and explanation
Correct answer: C. 7
Compare the direct route (9) with A–B–C (3+4=7); choose the smaller.
Q139. A weighted graph has edges A–B of weight 4, B–C of weight 5, and A–C of weight 10. What is the shortest A-to-C distance?
- A. 11
- B. 9
- C. 10
- D. 19
Show correct answer and explanation
Correct answer: B. 9
Compare the direct route (10) with A–B–C (4+5=9); choose the smaller.
Q140. A weighted graph has edges A–B of weight 5, B–C of weight 6, and A–C of weight 11. What is the shortest A-to-C distance?
- A. 11
- B. 12
- C. 22
- D. 13
Show correct answer and explanation
Correct answer: A. 11
Compare the direct route (11) with A–B–C (5+6=11); choose the smaller.
Q141. A weighted graph has edges A–B of weight 6, B–C of weight 7, and A–C of weight 12. What is the shortest A-to-C distance?
- A. 14
- B. 25
- C. 13
- D. 12
Show correct answer and explanation
Correct answer: D. 12
Compare the direct route (12) with A–B–C (6+7=13); choose the smaller.
Q142. A weighted graph has edges A–B of weight 7, B–C of weight 8, and A–C of weight 13. What is the shortest A-to-C distance?
- A. 28
- B. 14
- C. 13
- D. 16
Show correct answer and explanation
Correct answer: C. 13
Compare the direct route (13) with A–B–C (7+8=15); choose the smaller.
Q143. A weighted graph has edges A–B of weight 8, B–C of weight 9, and A–C of weight 14. What is the shortest A-to-C distance?
- A. 15
- B. 14
- C. 18
- D. 31
Show correct answer and explanation
Correct answer: B. 14
Compare the direct route (14) with A–B–C (8+9=17); choose the smaller.
Q144. A weighted graph has edges A–B of weight 9, B–C of weight 10, and A–C of weight 15. What is the shortest A-to-C distance?
- A. 15
- B. 20
- C. 34
- D. 16
Show correct answer and explanation
Correct answer: A. 15
Compare the direct route (15) with A–B–C (9+10=19); choose the smaller.
Floor & Ceiling Functions
Q145. Find ⌊3.7⌋.
- A. 2
- B. 5
- C. 3
- D. 4
Show correct answer and explanation
Correct answer: C. 3
The floor is the greatest integer not exceeding 3.7.
Q146. Find ⌈3.2⌉.
- A. 2
- B. 4
- C. 3
- D. 5
Show correct answer and explanation
Correct answer: B. 4
The ceiling is the least integer not less than 3.2.
Q147. Find ⌊4.7⌋.
- A. 6
- B. 4
- C. 5
- D. 3
Show correct answer and explanation
Correct answer: B. 4
The floor is the greatest integer not exceeding 4.7.
Q148. Find ⌈4.2⌉.
- A. 5
- B. 4
- C. 6
- D. 3
Show correct answer and explanation
Correct answer: A. 5
The ceiling is the least integer not less than 4.2.
Q149. Find ⌊5.7⌋.
- A. 5
- B. 6
- C. 4
- D. 7
Show correct answer and explanation
Correct answer: A. 5
The floor is the greatest integer not exceeding 5.7.
Q150. Find ⌈5.2⌉.
- A. 5
- B. 7
- C. 4
- D. 6
Show correct answer and explanation
Correct answer: D. 6
The ceiling is the least integer not less than 5.2.
Q151. Find ⌊6.7⌋.
- A. 7
- B. 5
- C. 8
- D. 6
Show correct answer and explanation
Correct answer: D. 6
The floor is the greatest integer not exceeding 6.7.
Q152. Find ⌈6.2⌉.
- A. 8
- B. 5
- C. 7
- D. 6
Show correct answer and explanation
Correct answer: C. 7
The ceiling is the least integer not less than 6.2.
Q153. Find ⌊7.7⌋.
- A. 6
- B. 9
- C. 7
- D. 8
Show correct answer and explanation
Correct answer: C. 7
The floor is the greatest integer not exceeding 7.7.
Q154. Find ⌈7.2⌉.
- A. 6
- B. 8
- C. 7
- D. 9
Show correct answer and explanation
Correct answer: B. 8
The ceiling is the least integer not less than 7.2.
Q155. Find ⌊8.7⌋.
- A. 10
- B. 8
- C. 9
- D. 7
Show correct answer and explanation
Correct answer: B. 8
The floor is the greatest integer not exceeding 8.7.
Q156. Find ⌈8.2⌉.
- A. 9
- B. 8
- C. 10
- D. 7
Show correct answer and explanation
Correct answer: A. 9
The ceiling is the least integer not less than 8.2.
Q157. Find ⌊9.7⌋.
- A. 9
- B. 10
- C. 8
- D. 11
Show correct answer and explanation
Correct answer: A. 9
The floor is the greatest integer not exceeding 9.7.
Q158. Find ⌈9.2⌉.
- A. 9
- B. 11
- C. 8
- D. 10
Show correct answer and explanation
Correct answer: D. 10
The ceiling is the least integer not less than 9.2.
Q159. Find ⌊10.7⌋.
- A. 11
- B. 9
- C. 12
- D. 10
Show correct answer and explanation
Correct answer: D. 10
The floor is the greatest integer not exceeding 10.7.
Q160. Find ⌈10.2⌉.
- A. 12
- B. 9
- C. 11
- D. 10
Show correct answer and explanation
Correct answer: C. 11
The ceiling is the least integer not less than 10.2.
Big O, Little o & Omega
Q161. For f(n)=2n^2+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(n^2)
- B. Θ(n^3)
- C. Θ(1)
- D. o(n^2)
Show correct answer and explanation
Correct answer: A. Θ(n^2)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^2.
Q162. For positive integers n→∞, which statement is correct? (2 is fixed)
- A. n^3 = o(n^2)
- B. n^2 = Θ(1)
- C. n^3 = O(n^2)
- D. n^2 = o(n^3)
Show correct answer and explanation
Correct answer: D. n^2 = o(n^3)
n^2/n^3=1/n→0, so the little-o statement holds.
Q163. For f(n)=3n^3+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(n^4)
- B. Θ(1)
- C. o(n^3)
- D. Θ(n^3)
Show correct answer and explanation
Correct answer: D. Θ(n^3)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^3.
Q164. For positive integers n→∞, which statement is correct? (3 is fixed)
- A. n^3 = Θ(1)
- B. n^4 = O(n^3)
- C. n^3 = o(n^4)
- D. n^4 = o(n^3)
Show correct answer and explanation
Correct answer: C. n^3 = o(n^4)
n^3/n^4=1/n→0, so the little-o statement holds.
Q165. For f(n)=4n^4+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(1)
- B. o(n^4)
- C. Θ(n^4)
- D. Θ(n^5)
Show correct answer and explanation
Correct answer: C. Θ(n^4)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^4.
Q166. For positive integers n→∞, which statement is correct? (4 is fixed)
- A. n^5 = O(n^4)
- B. n^4 = o(n^5)
- C. n^5 = o(n^4)
- D. n^4 = Θ(1)
Show correct answer and explanation
Correct answer: B. n^4 = o(n^5)
n^4/n^5=1/n→0, so the little-o statement holds.
Q167. For f(n)=5n^5+5n+1, which is a tight asymptotic bound as n→∞?
- A. o(n^5)
- B. Θ(n^5)
- C. Θ(n^6)
- D. Θ(1)
Show correct answer and explanation
Correct answer: B. Θ(n^5)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^5.
Q168. For positive integers n→∞, which statement is correct? (5 is fixed)
- A. n^5 = o(n^6)
- B. n^6 = o(n^5)
- C. n^5 = Θ(1)
- D. n^6 = O(n^5)
Show correct answer and explanation
Correct answer: A. n^5 = o(n^6)
n^5/n^6=1/n→0, so the little-o statement holds.
Q169. For f(n)=6n^6+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(n^6)
- B. Θ(n^7)
- C. Θ(1)
- D. o(n^6)
Show correct answer and explanation
Correct answer: A. Θ(n^6)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^6.
Q170. For positive integers n→∞, which statement is correct? (6 is fixed)
- A. n^7 = o(n^6)
- B. n^6 = Θ(1)
- C. n^7 = O(n^6)
- D. n^6 = o(n^7)
Show correct answer and explanation
Correct answer: D. n^6 = o(n^7)
n^6/n^7=1/n→0, so the little-o statement holds.
Q171. For f(n)=7n^7+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(n^8)
- B. Θ(1)
- C. o(n^7)
- D. Θ(n^7)
Show correct answer and explanation
Correct answer: D. Θ(n^7)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^7.
Q172. For positive integers n→∞, which statement is correct? (7 is fixed)
- A. n^7 = Θ(1)
- B. n^8 = O(n^7)
- C. n^7 = o(n^8)
- D. n^8 = o(n^7)
Show correct answer and explanation
Correct answer: C. n^7 = o(n^8)
n^7/n^8=1/n→0, so the little-o statement holds.
Q173. For f(n)=8n^8+5n+1, which is a tight asymptotic bound as n→∞?
- A. Θ(1)
- B. o(n^8)
- C. Θ(n^8)
- D. Θ(n^9)
Show correct answer and explanation
Correct answer: C. Θ(n^8)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^8.
Q174. For positive integers n→∞, which statement is correct? (8 is fixed)
- A. n^9 = O(n^8)
- B. n^8 = o(n^9)
- C. n^9 = o(n^8)
- D. n^8 = Θ(1)
Show correct answer and explanation
Correct answer: B. n^8 = o(n^9)
n^8/n^9=1/n→0, so the little-o statement holds.
Q175. For f(n)=9n^9+5n+1, which is a tight asymptotic bound as n→∞?
- A. o(n^9)
- B. Θ(n^9)
- C. Θ(n^10)
- D. Θ(1)
Show correct answer and explanation
Correct answer: B. Θ(n^9)
A polynomial with positive leading coefficient grows at the rate of its highest power, n^9.
Q176. For positive integers n→∞, which statement is correct? (9 is fixed)
- A. n^9 = o(n^10)
- B. n^10 = o(n^9)
- C. n^9 = Θ(1)
- D. n^10 = O(n^9)
Show correct answer and explanation
Correct answer: A. n^9 = o(n^10)
n^9/n^10=1/n→0, so the little-o statement holds.
Increasing & Decreasing Functions
Q177. On the real numbers, classify f(x)=2x+1.
- A. Constant
- B. Neither increasing nor decreasing
- C. Strictly increasing
- D. Strictly decreasing
Show correct answer and explanation
Correct answer: C. Strictly increasing
The slope 2 is positive, so f increases strictly.
Q178. On the real numbers, classify f(x)=3x+2.
- A. Neither increasing nor decreasing
- B. Strictly increasing
- C. Strictly decreasing
- D. Constant
Show correct answer and explanation
Correct answer: B. Strictly increasing
The slope 3 is positive, so f increases strictly.
Q179. On the real numbers, classify f(x)=4x+3.
- A. Strictly increasing
- B. Strictly decreasing
- C. Constant
- D. Neither increasing nor decreasing
Show correct answer and explanation
Correct answer: A. Strictly increasing
The slope 4 is positive, so f increases strictly.
Q180. On the real numbers, classify f(x)=5x+4.
- A. Strictly decreasing
- B. Constant
- C. Neither increasing nor decreasing
- D. Strictly increasing
Show correct answer and explanation
Correct answer: D. Strictly increasing
The slope 5 is positive, so f increases strictly.
Q181. On the real numbers, classify f(x)=6x+5.
- A. Constant
- B. Neither increasing nor decreasing
- C. Strictly increasing
- D. Strictly decreasing
Show correct answer and explanation
Correct answer: C. Strictly increasing
The slope 6 is positive, so f increases strictly.
Q182. On the real numbers, classify f(x)=7x+6.
- A. Neither increasing nor decreasing
- B. Strictly increasing
- C. Strictly decreasing
- D. Constant
Show correct answer and explanation
Correct answer: B. Strictly increasing
The slope 7 is positive, so f increases strictly.
Q183. On the real numbers, classify f(x)=8x+7.
- A. Strictly increasing
- B. Strictly decreasing
- C. Constant
- D. Neither increasing nor decreasing
Show correct answer and explanation
Correct answer: A. Strictly increasing
The slope 8 is positive, so f increases strictly.
Q184. On the real numbers, classify f(x)=9x+8.
- A. Strictly decreasing
- B. Constant
- C. Neither increasing nor decreasing
- D. Strictly increasing
Show correct answer and explanation
Correct answer: D. Strictly increasing
The slope 9 is positive, so f increases strictly.
Power Functions
Q185. For f(x)=x², find f(2).
- A. 7
- B. 4
- C. 5
- D. 6
Show correct answer and explanation
Correct answer: B. 4
Squaring 2 gives 4.
Q186. For f(x)=x², find f(3).
- A. 9
- B. 6
- C. 10
- D. 5
Show correct answer and explanation
Correct answer: A. 9
Squaring 3 gives 9.
Q187. For f(x)=x², find f(4).
- A. 8
- B. 17
- C. 6
- D. 16
Show correct answer and explanation
Correct answer: D. 16
Squaring 4 gives 16.
Q188. For f(x)=x², find f(5).
- A. 26
- B. 7
- C. 25
- D. 10
Show correct answer and explanation
Correct answer: C. 25
Squaring 5 gives 25.
Q189. For f(x)=x², find f(6).
- A. 8
- B. 36
- C. 12
- D. 37
Show correct answer and explanation
Correct answer: B. 36
Squaring 6 gives 36.
Q190. For f(x)=x², find f(7).
- A. 49
- B. 14
- C. 50
- D. 9
Show correct answer and explanation
Correct answer: A. 49
Squaring 7 gives 49.
Q191. For f(x)=x², find f(8).
- A. 16
- B. 65
- C. 10
- D. 64
Show correct answer and explanation
Correct answer: D. 64
Squaring 8 gives 64.
Q192. For f(x)=x², find f(9).
- A. 82
- B. 11
- C. 81
- D. 18
Show correct answer and explanation
Correct answer: C. 81
Squaring 9 gives 81.
Connectivity
Q193. Which statement about a connected undirected graph with 4 vertices is correct?
- A. There is a path between every pair of vertices.
- B. Every vertex has degree 3.
- C. It has no cycles.
- D. All edges have equal weights.
Show correct answer and explanation
Correct answer: A. There is a path between every pair of vertices.
This path condition is exactly the definition of connectedness.
Q194. A graph with exactly two connected components is what?
- A. Connected
- B. Disconnected
- C. Complete
- D. A tree
Show correct answer and explanation
Correct answer: B. Disconnected
A connected graph has exactly one connected component.
Q195. In an undirected graph, if there is a path from u to v, what must also exist?
- A. A path from v to u
- B. A loop at u
- C. An edge joining u and v directly
- D. An Euler circuit
Show correct answer and explanation
Correct answer: A. A path from v to u
An undirected path can be traversed in reverse.
Q196. How many connected components does a tree have?
- A. 0
- B. 2
- C. 1
- D. One per edge
Show correct answer and explanation
Correct answer: C. 1
A tree is connected by definition.
Q197. Which graph is necessarily connected?
- A. A graph with no edges on five vertices
- B. A disjoint union of two cycles
- C. A graph containing an isolated vertex and other vertices
- D. The complete graph K6
Show correct answer and explanation
Correct answer: D. The complete graph K6
Each pair of vertices of a complete graph is directly adjacent.
Q198. Can a connected graph with 6 vertices have only 4 edges?
- A. Yes, always
- B. No
- C. Only if it has loops
- D. Only if all degrees are even
Show correct answer and explanation
Correct answer: B. No
Any connected graph with n vertices has at least n−1 edges, here 5.
Q199. What is a bridge in a connected undirected graph?
- A. An edge whose removal disconnects the graph
- B. Any edge in a cycle
- C. A vertex of degree zero
- D. An edge joining a vertex to itself
Show correct answer and explanation
Correct answer: A. An edge whose removal disconnects the graph
A bridge is an edge whose deletion increases the number of connected components.
Q200. What is a spanning tree of a connected graph with 8 vertices?
- A. A cycle of length 8
- B. A subgraph with 8 edges
- C. A connected acyclic subgraph containing all 8 vertices
- D. Any disconnected forest
Show correct answer and explanation
Correct answer: C. A connected acyclic subgraph containing all 8 vertices
A spanning tree includes all vertices, is connected and acyclic, and has 7 edges.
Interactive MCQ Practice
Practise one MCQ at a time. Reveal the correct answer and explanation before proceeding to the next question.
Start Combinatorics and Graph Theory — One Question at a Time