BCS Discrete Mathematics 3 — Questions and Answers
Question 1: Which of the following statements about trees in graph theory is true?
- A tree with n vertices has n edges
- A tree with n vertices has n-1 edges (Correct answer)
- A tree must have at least one cycle
- All trees are bipartite only if they have even vertices
Correct answer: A tree with n vertices has n-1 edges
A tree is a connected acyclic graph; a tree with n vertices always has exactly n-1 edges.
Question 2: What is 17 mod 5?
- 1
- 2 (Correct answer)
- 3
- 4
Correct answer: 2
17 divided by 5 gives quotient 3 and remainder 2, so 17 mod 5 = 2.
Question 3: Which of the following correctly expresses De Morgan's law for sets?
- (A ∪ B)' = A' ∪ B'
- (A ∩ B)' = A' ∩ B'
- (A ∪ B)' = A' ∩ B' (Correct answer)
- (A ∩ B)' = A ∪ B
Correct answer: (A ∪ B)' = A' ∩ B'
De Morgan's law for sets states (A ∪ B)' = A' ∩ B'; the complement of a union equals the intersection of complements.
Question 4: In how many ways can a committee of 3 be chosen from a group of 7 people?
- 21
- 35 (Correct answer)
- 42
- 210
Correct answer: 35
Using combinations: C(7,3) = 7! / (3! × 4!) = 35, since the order of selection does not matter.
Question 5: Which quantifier asserts that a property holds for all elements in the domain?
- Existential quantifier (∃)
- Universal quantifier (∀) (Correct answer)
- Unique quantifier (∃!)
- Bounded quantifier
Correct answer: Universal quantifier (∀)
The universal quantifier ∀ (for all) asserts that the given predicate is true for every element in the specified domain.
Question 6: A relation that is reflexive, antisymmetric, and transitive is called a:
- Equivalence relation
- Partial order (Correct answer)
- Total order
- Bijective relation
Correct answer: Partial order
A partial order is defined as a relation that is reflexive, antisymmetric, and transitive; the ≤ relation on integers is a classic example.
Question 7: What is the chromatic number of a cycle graph C_5 (a cycle with 5 vertices)?
- 1
- 2
- 3 (Correct answer)
- 4
Correct answer: 3
C_5 is an odd cycle, so it cannot be 2-colored; the minimum number of colors needed to properly color C_5 is 3.
BCS Discrete Mathematics 3
Which of the following statements about trees in graph theory is true?