Discrete Mathematics Exam Review: Key Concepts and Proofs

Eulerian Circuits and Paths

Eulerian Circuit: Exists if and only if the graph is connected AND every vertex has an even degree.

Eulerian Trail: Exists if and only if the graph is connected AND exactly two vertices have an odd degree. (Start and end at the odd-degree vertices.)

Exam Examples

• Graph A: Has an Euler trail (4→5→3→4→2→3→1→6→5→2→6). Exactly two odd-degree vertices exist.
• Graph B: No Euler trail or circuit. Vertices 1, 2, 5, and 6 have odd degrees (four total).

Problem Solving Steps

1. Check if the sum of degrees is even (Handshake Theorem).
2. Calculate the number of edges (Sum of degrees / 2).
3. Construct the path or identify a contradiction.

Negations and Quantifiers

¬(∀x, P(x))

≡ ∃x such that ¬P(x)

¬(∃x, P(x))

≡ ∀x, ¬P(x)

¬(P→Q)

≡ P ∧ ¬Q

¬(P∧Q)

≡ ¬P ∨ ¬Q (De Morgan's Law)

¬(P∨Q)

≡ ¬P ∧ ¬Q (De Morgan's Law)

Exam Q3: Negate "∀ rational a,b: ab is rational" → ∃ rational a,b such that ab is not rational.

Sets and Symmetric Difference

A−B

Elements in A but not in B.

A∆B

(A−B) ∪ (B−A) = "XOR of sets".

A∩B

Elements in both sets.

A∪B

Elements in either set.

Exam Q4: A = {1,2,3,4,5}, B = {1,3,5,7,9}. A∆B = {2, 4, 7, 9}.

Counting and Combinatorics

Permutation

P(n,r) = n!/(n−r)! (Ordered, no repetition).

Combination

C(n,r) = n! / (r!(n−r)!) (Unordered).

Multiplication Principle

If there are k choices at each stage, multiply them.

Stars and Bars

n identical items in r distinct bins: C(n+r−1, r−1).

Direct Proof Template

Exam Q6: Prove the sum of three consecutive even integers is a multiple of 6.

Let p=2k, q=2k+2, r=2k+4 for integer k. Then p+q+r = 6k+6 = 6(k+1). Since k+1 is an integer, the sum is a multiple of 6. □

Functions: Injective and Surjective

One-to-one (Injective)

f(a)=f(b) ⟹ a=b.

Onto (Surjective)

Every y∈Y has some x such that f(x)=y.

Bijection

Both 1-1 and onto; therefore, invertible.

Inverse

f(f(x))=x means f is its own inverse.

Mathematical Induction

• Base case: Verify the claim for n=0 or n=1.
• Inductive hypothesis (IH): Assume the claim is true for n=k.
• Inductive step: Show it is true for n=k+1 using the IH.

Exam Q9: Prove 5ⁿ+3 is divisible by 4 for all n≥0.

• Base: n=0: 5⁰+3=4 (divisible by 4).
• IH: Assume 4|(5ᵏ+3), so 5ᵏ+3=4m.
• Step: 5ᵏ⁺¹+3 = 5(5ᵏ)+3 = 5(4m−3)+3 = 20m−15+3 = 20m−12 = 4(5m−3). Since 5m−3 ∈ ℤ, 4|(5ᵏ⁺¹+3). □