Discrete Mathematics 2022

Answer: (ii) {2,3}

Solution: A ∩ B contains elements common to both A and B.

Answer: (ii) 2^(m×n)

Solution: A relation is a subset of A × B. |A × B| = m × n, so number of subsets = 2^(m×n).

Answer: (ii) Every element of B has a preimage

Solution: A surjective function maps to every element of the codomain; range = codomain.

Answer: (iii) 10

Solution: Number of edges in Kₙ = n(n-1)/2 = 5×4/2 = 10.

Answer: (ii) ¬q → ¬p

Solution: The contrapositive of p → q is ¬q → ¬p, and it is logically equivalent to the original.

Answer: (i) Lattice

Solution: A lattice is a POSET where every pair has a least upper bound (join) and greatest lower bound (meet).

Answer: (i) 0

Solution: In (Z, +), a + 0 = 0 + a = a for all a ∈ Z. So 0 is the identity element.

Answer: (ii) 2ⁿ

Solution: aₙ = 2aₙ₋₁ = 2²aₙ₋₂ = ... = 2ⁿa₀ = 2ⁿ × 1 = 2ⁿ

Answer: (i) n - 1

Solution: A tree with n vertices always has exactly n - 1 edges. This is a fundamental property of trees.

Answer: (i) 1

Solution: By complement law, a + a' = 1 (an element OR its complement always equals 1).

Answer:

Propositional Logic: A formal system dealing with propositions (statements that are true or false) and logical connectives.

Connectives:

• ¬ (NOT), ∧ (AND), ∨ (OR), → (implies), ↔ (biconditional)

Proof by Truth Table:

The last column (Full = [(p→q)∧(q→r)] → (p→r)) is always T. Hence, it is a tautology. ✓

This is the Hypothetical Syllogism — a fundamental rule of inference.

Answer:

Predicate Logic: Extends propositional logic with predicates (properties of objects) and quantifiers.

Predicates: P(x) is a statement about variable x. E.g., P(x): "x is prime"

Quantifiers:

• Universal quantifier (∀): ∀x P(x) means "P(x) is true for all x"
  • Example: ∀x (x² ≥ 0) — "all squares are non-negative"
• Existential quantifier (∃): ∃x P(x) means "there exists an x for which P(x) is true"
  • Example: ∃x (x² = 4) — "there exists x whose square is 4"

De Morgan's Laws for Quantifiers:

1. ¬(∀x P(x)) ≡ ∃x ¬P(x)
2. ¬(∃x P(x)) ≡ ∀x ¬P(x)

Proof of ¬(∀x P(x)) ≡ ∃x ¬P(x):

Let domain D = {a₁, a₂, ..., aₙ}

∀x P(x) ≡ P(a₁) ∧ P(a₂) ∧ ... ∧ P(aₙ)

¬(∀x P(x)) ≡ ¬(P(a₁) ∧ P(a₂) ∧ ... ∧ P(aₙ)) ≡ ¬P(a₁) ∨ ¬P(a₂) ∨ ... ∨ ¬P(aₙ) [De Morgan's] ≡ ∃x ¬P(x)

Hence proved: ¬(∀x P(x)) ≡ ∃x ¬P(x) ✓

Intuition: "Not everything has property P" is equivalent to "Something doesn't have property P."

Answer:

Let R be a relation on set A.

Reflexive: (a, a) ∈ R for every a ∈ A

• Example: A = {1,2,3}, R = {(1,1),(2,2),(3,3),(1,2)} ✓ reflexive

Symmetric: If (a, b) ∈ R, then (b, a) ∈ R

• Example: R = {(1,2),(2,1),(1,1)} ✓ symmetric

Transitive: If (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R

• Example: R = {(1,2),(2,3),(1,3)} ✓ transitive

Antisymmetric: If (a, b) ∈ R and (b, a) ∈ R, then a = b

• Example: ≤ on integers. If a ≤ b and b ≤ a, then a = b

Equivalence Relation: A relation that is reflexive, symmetric, AND transitive.

• Example: Congruence modulo n. On Z, a ≡ b (mod 3):
  • Reflexive: a ≡ a (mod 3) ✓
  • Symmetric: if a ≡ b (mod 3) then b ≡ a (mod 3) ✓
  • Transitive: if a ≡ b and b ≡ c (mod 3) then a ≡ c (mod 3) ✓
• Equivalence classes: [0]={...-3,0,3,6...}, [1]={...-2,1,4,7...}, [2]={...-1,2,5,8...}

Answer:

Partial Order Relation (POSET): A relation that is reflexive, antisymmetric, and transitive. Denoted (A, ≤) or (A, R).

Example: Divisibility relation on positive integers: a | b ("a divides b")

• Reflexive: a | a ✓
• Antisymmetric: if a | b and b | a, then a = b ✓
• Transitive: if a | b and b | c, then a | c ✓

Hasse Diagram for (A = {1,2,3,4,6,8,12,24}, |):

            24
          /    \
        12      8
       / \      |
      6   4     |
     / \ / \   /
    3   2    
     \ /
      1

More precisely:

• 1 divides: 2, 3, 4, 6, 8, 12, 24
• 2 divides: 4, 6, 8, 12, 24
• 3 divides: 6, 12, 24
• 4 divides: 8, 12, 24
• 6 divides: 12, 24
• 8 divides: 24
• 12 divides: 24

Hasse diagram shows only direct (covering) relations:

• 1 → 2, 1 → 3
• 2 → 4, 2 → 6
• 3 → 6
• 4 → 8, 4 → 12
• 6 → 12
• 8 → 24
• 12 → 24

Properties of this POSET:

• Greatest element: 24
• Least element: 1
• This is a lattice (every pair has LUB and GLB)

Answer:

Injection (One-to-one): f(a₁) = f(a₂) ⟹ a₁ = a₂

• Different inputs give different outputs
• |A| ≤ |B|

Surjection (Onto): For every b ∈ B, ∃a ∈ A such that f(a) = b

• Every element of B is mapped to
• |A| ≥ |B|

Bijection: Both injective and surjective

• One-to-one correspondence
• |A| = |B|

Proof: f has inverse ⟺ f is bijection

(⟹) If f has inverse f⁻¹, then f is a bijection:

f⁻¹ exists means f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B

Injective: Suppose f(a₁) = f(a₂). Then f⁻¹(f(a₁)) = f⁻¹(f(a₂)), so a₁ = a₂. ✓

Surjective: For any b ∈ B, let a = f⁻¹(b). Then f(a) = f(f⁻¹(b)) = b. ✓

(⟸) If f is a bijection, then f has an inverse:

Since f is surjective, for each b ∈ B, ∃a ∈ A with f(a) = b. Since f is injective, this a is unique. Define f⁻¹(b) = a. This is well-defined because a is unique. Then f⁻¹ ∘ f = id_A and f ∘ f⁻¹ = id_B. ✓

Answer:

Pigeonhole Principle: If n+1 (or more) objects are placed into n boxes, then at least one box contains 2 or more objects.

Generalized form: If N objects are placed into k boxes, at least one box contains ⌈N/k⌉ objects.

Proof: By contradiction. Assume each of the n boxes contains at most 1 object. Then total objects ≤ n × 1 = n. But we have n+1 objects, a contradiction. Hence at least one box has ≥ 2 objects. ✓

Application 1: Birthdays Among 367 people, at least two share the same birthday. (366 possible birthdays + 1 extra person → pigeonhole principle guarantees a collision.)

Application 2: Socks A drawer has 10 red and 10 blue socks. To guarantee getting a matching pair, draw 3 socks. (2 colors as boxes, 3 socks as objects → one color has ≥ 2 socks.)

Application 3: Integers Among any 5 integers, at least two have the same remainder when divided by 4. (4 possible remainders, 5 integers → guaranteed collision.)

Answer:

Graph: G = (V, E) where V = set of vertices, E = set of edges.

Types:

• Simple graph: No loops, no multiple edges
• Multigraph: Multiple edges allowed between vertices
• Complete graph (Kₙ): Every vertex connected to every other
• Bipartite graph: Vertices divided into two disjoint sets, edges only between sets
• Complete bipartite (Km,n): Every vertex of one set connected to every vertex of other

Handshaking Theorem: In any graph G = (V, E), the sum of degrees of all vertices equals twice the number of edges:

$$\sum_{v \in V} \deg(v) = 2|E|$$

Proof: Each edge e = {u, v} contributes exactly 1 to deg(u) and 1 to deg(v). So each edge contributes 2 to the total sum of degrees. With |E| edges, the total sum = 2|E|. ✓

Corollary: The number of vertices with odd degree is always even.

Example: Triangle graph K₃:

• deg(v₁) + deg(v₂) + deg(v₃) = 2 + 2 + 2 = 6 = 2 × 3 = 2|E| ✓

Answer:

Euler Path: A path that visits every EDGE exactly once. Euler Circuit: An Euler path that starts and ends at the same vertex.

Conditions for Euler Path/Circuit:

• Euler Circuit exists ⟺ Graph is connected AND every vertex has even degree
• Euler Path exists ⟺ Graph is connected AND has exactly 0 or 2 vertices of odd degree
  • If 0 odd-degree vertices → Euler circuit (which is also a path)
  • If 2 odd-degree vertices → Euler path (starts at one, ends at other)

Hamiltonian Path: A path that visits every VERTEX exactly once. Hamiltonian Circuit: A Hamiltonian path that starts and ends at the same vertex.

Conditions (no simple necessary and sufficient conditions):

• Dirac's Theorem: If |V| ≥ 3 and deg(v) ≥ n/2 for all v, then G has a Hamiltonian circuit.
• Ore's Theorem: If |V| ≥ 3 and deg(u) + deg(v) ≥ n for all non-adjacent u, v, then G has a Hamiltonian circuit.

Answer:

Tree: A connected acyclic undirected graph.

Properties:

1. Between any two vertices, there is exactly one path
2. A tree with n vertices has exactly n-1 edges
3. Removing any edge disconnects the tree
4. Adding any edge creates exactly one cycle
5. A tree is a minimally connected graph

Proof: A tree with n vertices has n-1 edges.

By induction on n:

Base case: n = 1. A single vertex has 0 = 1-1 edges. ✓

Inductive step: Assume true for all trees with k < n vertices.

Let T be a tree with n vertices (n ≥ 2).

Since T is a tree with n ≥ 2, T has at least one leaf (vertex of degree 1). [Proof: If all vertices had degree ≥ 2, by handshaking theorem, 2|E| ≥ 2n, so |E| ≥ n. But a tree is acyclic, so |E| ≤ n-1. Contradiction.]

Let v be a leaf. Remove v and its incident edge to get T'. T' is connected (removing a leaf doesn't disconnect). T' is acyclic (subgraph of acyclic graph is acyclic). So T' is a tree with n-1 vertices.

By induction hypothesis, T' has (n-1)-1 = n-2 edges. T has one more edge than T', so T has n-2+1 = n-1 edges. ✓

Answer:

Spanning Tree: A subgraph that is a tree and contains all vertices of the original graph.

Properties:

• Contains all V vertices
• Has exactly V-1 edges
• Is connected and acyclic
• A graph may have multiple spanning trees

Kruskal's Algorithm:

1. Sort all edges by weight
2. Pick the smallest edge; if it doesn't form a cycle, add it
3. Repeat until V-1 edges are selected

Example: Graph with vertices {A,B,C,D,E} and edges:

Sorted edges: A-B(1), B-D(2), A-C(3), B-C(4), C-D(5), C-E(6), D-E(7)

Selection:

1. A-B (1): No cycle → Add ✓
2. B-D (2): No cycle → Add ✓
3. A-C (3): No cycle → Add ✓
4. B-C (4): Forms cycle A-B-C-A → Skip ✗
5. C-D (5): Forms cycle → Skip ✗
6. C-E (6): No cycle → Add ✓ (V-1 = 4 edges selected)

MST edges: {A-B, B-D, A-C, C-E} Total weight = 1 + 2 + 3 + 6 = 12

Time Complexity: O(E log E) for sorting

Answer:

Group: A set G with binary operation * satisfying:

1. Closure: a * b ∈ G for all a, b ∈ G
2. Associativity: (a * b) * c = a * (b * c)
3. Identity: ∃e ∈ G such that a * e = e * a = a
4. Inverse: For each a ∈ G, ∃a⁻¹ ∈ G such that a * a⁻¹ = a⁻¹ * a = e

Abelian Group: A group where operation is commutative: a * b = b * a

Subgroup: A subset H of G that is itself a group under the same operation.

Proof that (Z₄, +₄) is a group: Z₄ = {0, 1, 2, 3}, operation is addition modulo 4.

Cayley Table:

1. Closure: All entries are in Z₄ ✓
2. Associativity: Modular addition is associative ✓
3. Identity: 0 is the identity (a + 0 = a for all a) ✓
4. Inverse: 0⁻¹=0, 1⁻¹=3, 2⁻¹=2, 3⁻¹=1 ✓

Also Abelian: Table is symmetric about diagonal ✓

Answer:

Lagrange's Theorem: If G is a finite group and H is a subgroup of G, then |H| divides |G|.

Moreover, |G| / |H| = number of distinct left cosets of H in G.

Proof:

Let G be a finite group, H a subgroup of G.

Step 1: Define left cosets. For a ∈ G, the left coset aH = {ah : h ∈ H}.

Step 2: All cosets have the same size. Define φ: H → aH by φ(h) = ah. This is a bijection:

• Injective: ah₁ = ah₂ ⟹ h₁ = h₂ (left cancellation) ✓
• Surjective: By definition of aH ✓ So |aH| = |H|.

Step 3: Distinct cosets partition G.

• Every element a ∈ G belongs to coset aH (since a = ae ∈ aH)
• Two cosets are either identical or disjoint: If aH ∩ bH ≠ ∅, then ∃h₁,h₂ with ah₁ = bh₂, so a = bh₂h₁⁻¹ ∈ bH, hence aH = bH.

Step 4: Let there be k distinct cosets. Then: |G| = k × |H|

Therefore |H| divides |G|. ✓

Corollary: The order of every element divides the order of the group.

Answer:

Step 1: Characteristic equation Replace aₙ with rⁿ: rⁿ - 5rⁿ⁻¹ + 6rⁿ⁻² = 0 r² - 5r + 6 = 0 (r - 2)(r - 3) = 0 r₁ = 2, r₂ = 3

Step 2: General solution aₙ = C₁ · 2ⁿ + C₂ · 3ⁿ

Step 3: Apply initial conditions

a₀ = 1: C₁ · 1 + C₂ · 1 = 1 → C₁ + C₂ = 1 ... (i)

a₁ = 4: C₁ · 2 + C₂ · 3 = 4 → 2C₁ + 3C₂ = 4 ... (ii)

From (i): C₁ = 1 - C₂ Substitute in (ii): 2(1 - C₂) + 3C₂ = 4 2 - 2C₂ + 3C₂ = 4 C₂ = 2 C₁ = 1 - 2 = -1

Solution: aₙ = -2ⁿ + 2 · 3ⁿ = 2 · 3ⁿ - 2ⁿ

Verification:

• a₀ = 2(1) - 1 = 1 ✓
• a₁ = 2(3) - 2 = 4 ✓
• a₂ = 2(9) - 4 = 14
• Check: a₂ = 5a₁ - 6a₀ = 20 - 6 = 14 ✓

Answer:

Step 1: Solve homogeneous part aₙ - 2aₙ₋₁ = 0 Characteristic equation: r - 2 = 0, r = 2 Homogeneous solution: aₙ⁽ʰ⁾ = C · 2ⁿ

Step 2: Find particular solution Since f(n) = 3ⁿ and 3 is not a root of the characteristic equation: Try aₙ⁽ᵖ⁾ = A · 3ⁿ

Substitute: A · 3ⁿ = 2A · 3ⁿ⁻¹ + 3ⁿ A · 3ⁿ = (2A/3) · 3ⁿ + 3ⁿ A = 2A/3 + 1 A - 2A/3 = 1 A/3 = 1 A = 3

Particular solution: aₙ⁽ᵖ⁾ = 3 · 3ⁿ = 3ⁿ⁺¹

Step 3: General solution aₙ = C · 2ⁿ + 3ⁿ⁺¹

Step 4: Apply initial condition a₀ = 1: 1 = C · 1 + 3¹ 1 = C + 3 C = -2

Solution: aₙ = -2 · 2ⁿ + 3ⁿ⁺¹ = 3ⁿ⁺¹ - 2ⁿ⁺¹

Verification:

• a₀ = 3 - 2 = 1 ✓
• a₁ = 9 - 4 = 5
• Check: a₁ = 2a₀ + 3¹ = 2 + 3 = 5 ✓

Answer:

Two graphs G₁ = (V₁, E₁) and G₂ = (V₂, E₂) are isomorphic if there exists a bijection f: V₁ → V₂ such that (u, v) ∈ E₁ ⟺ (f(u), f(v)) ∈ E₂.

Necessary conditions for isomorphism:

1. Same number of vertices
2. Same number of edges
3. Same degree sequence
4. Same number of cycles of each length
5. Complement graphs are also isomorphic

Example: G₁ with edges {(a,b),(b,c),(c,d),(d,a)} and G₂ with edges {(1,2),(2,3),(3,4),(4,1)} are isomorphic under f(a)=1, f(b)=2, f(c)=3, f(d)=4.

Note: Checking graph isomorphism is neither known to be in P nor NP-Complete.

Answer:

A planar graph is one that can be drawn on a plane without edge crossings.

Euler's Formula: For a connected planar graph: V - E + F = 2 where V = vertices, E = edges, F = faces (including outer face)

Corollaries:

1. For simple connected planar graph with V ≥ 3: E ≤ 3V - 6
2. K₅ and K₃,₃ are NOT planar
3. Kuratowski's Theorem: A graph is planar ⟺ it contains no subdivision of K₅ or K₃,₃

Example: K₄ is planar. V = 4, E = 6, F = 4 (3 inner triangles + 1 outer) V - E + F = 4 - 6 + 4 = 2 ✓

Answer:

Ring (R, +, ·): A set R with two binary operations satisfying:

1. (R, +) is an Abelian group
2. Multiplication is associative
3. Distributive: a·(b+c) = a·b + a·c and (a+b)·c = a·c + b·c

Commutative Ring: Multiplication is commutative Ring with Unity: Has multiplicative identity (1)

Example: (Z, +, ×) is a commutative ring with unity.

Field: A commutative ring with unity where every non-zero element has a multiplicative inverse.

Examples:

• (Q, +, ×) — field of rationals ✓
• (Z, +, ×) — NOT a field (2 has no inverse in Z)
• (Zₚ, +, ×) where p is prime — field ✓

Relationship: Every field is a ring, but not every ring is a field.

Answer:

The chromatic number χ(G) of a graph G is the minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color.

Properties:

1. χ(Kₙ) = n (complete graph needs n colors)
2. χ(bipartite) = 2 (if at least one edge exists)
3. χ(tree) = 2 (trees are bipartite)
4. χ(cycle Cₙ) = 2 if n even, 3 if n odd
5. χ(G) ≤ Δ(G) + 1 (Brook's theorem, with exceptions)

Four Color Theorem: Every planar graph can be colored with at most 4 colors: χ(G) ≤ 4.

Chromatic Polynomial: P(G, k) gives the number of proper colorings using k colors.

• For Kₙ: P(Kₙ, k) = k(k-1)(k-2)...(k-n+1)
• For tree with n vertices: P(T, k) = k(k-1)ⁿ⁻¹