Discrete Mathematics

Discrete Mathematics explores the study of distinct, countable structures rather than continuous ones, covering core areas like set theory, graph theory, combinatorics, and logic that form the mathematical backbone of computer science. It examines how these structures model real-world problems, from analyzing algorithm efficiency to representing networks, relationships, and decision-making processes through precise logical frameworks. This field blends abstract reasoning with practical application, showing how discrete structures provide the essential tools for proving algorithm correctness, designing efficient systems, and solving computational problems. At its core, discrete mathematics asks how we can model and reason about systems built from distinct, separate components rather than smooth, continuous change. Where separate pieces reveal the logic connecting them.

wwww

Chapter 1: What is Discrete Mathematics?

1.1 Definition and Importance

Discrete mathematics is the study of mathematical structures that are separate and countable. The word “discrete” means individual or distinct – like separate marbles in a bag, not a smooth continuous liquid.

A simple way to think about it:

Imagine you have a bag of apples. You can count them: 1 apple, 2 apples, 3 apples. There is no “half an apple” when counting whole apples. That is discrete.

Now imagine water pouring from a tap. You cannot count the water in “drops” easily – it flows continuously. That is continuous mathematics (like calculus).

Why is discrete math important?
Computers are discrete machines. They work with 0s and 1s – separate, distinct values. They cannot process infinite continuous values directly. Everything a computer does – from storing a photo to sending an email – uses discrete math.

1.2 Why Computer Scientists Need Discrete Math

Here are the real reasons you must learn discrete math if you want to be good at computer science:

Computer Science Topic	Discrete Math Foundation
Algorithms	Logic, proofs, recurrence relations
Data structures	Sets, functions, graphs, trees
Databases	Relations, sets
Cryptography	Number theory, modular arithmetic
Artificial intelligence	Logic, probability, combinatorics
Computer networks	Graph theory
Programming languages	Logic, sets, functions
Compilers	Trees, graphs

Example:
When you play a game of chess against a computer, the computer uses discrete math to decide its next move. It looks at all possible moves (countable options), not a continuous range.

1.3 Continuous vs. Discrete – A Simple Comparison

Feature	Continuous Math (Calculus)	Discrete Math
Values	Smooth, infinite, fractions allowed	Separate, countable, whole numbers
Example	Temperature during the day (25.1°, 25.11°, 25.111°)	Number of students in a class (1, 2, 3, …)
Graph	A smooth curve	Separate dots
Used for	Physics, engineering, weather	Computer science, logic, networks

Chapter 2: Logic – The Science of Correct Reasoning

Logic is the foundation of all mathematics and computer programming. It tells us how to think correctly.

2.1 Statements and Propositions

A proposition (or statement) is a sentence that is either true or false – but not both.

Examples of propositions:

• “The sky is blue.” (True)
• “5 is greater than 10.” (False)
• “Paris is the capital of France.” (True)
• “Today is Monday.” (True or False depending on the day)

Not propositions (questions or commands):

• “Close the door.” (Command – not true/false)
• “What time is it?” (Question – not true/false)
• “x + 5 = 10” (Not a proposition because x is unknown – this is a predicate, which we will learn later)

2.2 Logical Connectives (AND, OR, NOT, etc.)

We can combine simple propositions to make more complex ones using logical connectives.

Let P and Q represent propositions. Each can be T (true) or F (false).

Connective	Symbol	Meaning	Example
NOT (negation)	¬P or ~P	Opposite of P	If P = “It is raining”, then ¬P = “It is NOT raining”
AND (conjunction)	P ∧ Q	Both P AND Q are true	“It is raining AND it is cold”
OR (disjunction)	P ∨ Q	At least one is true (P or Q or both)	“It is raining OR it is cold”
XOR (exclusive or)	P ⊕ Q	Exactly one is true (not both)	“You can have juice XOR soda” (not both)
IMPLIES (conditional)	P → Q	If P is true, then Q must be true	“If it rains, then I take an umbrella”
BICONDITIONAL	P ↔ Q	P and Q are the same (both true or both false)	“It is raining if and only if the ground is wet”

2.3 Truth Tables – Visualizing Logic

A truth table shows all possible truth values of a logical expression.

NOT (¬P):

P	¬P
T	F
F	T

AND (P ∧ Q):

P	Q	P ∧ Q
T	T	T
T	F	F
F	T	F
F	F	F

Only when BOTH are true, AND is true.

OR (P ∨ Q):

P	Q	P ∨ Q
T	T	T
T	F	T
F	T	T
F	F	F

OR is true when AT LEAST ONE is true.

IMPLIES (P → Q):

P	Q	P → Q
T	T	T
T	F	F
F	T	T
F	F	T

This is tricky! An implication is only false when P is true and Q is false. If P is false, the statement is considered true (vacuously true).

Example: “If 2+2=5 (false), then I am the king of the world.” This statement is considered true in logic!

BICONDITIONAL (P ↔ Q):

P	Q	P ↔ Q
T	T	T
T	F	F
F	T	F
F	F	T

True when P and Q match.

2.4 Logical Equivalence

Two logical expressions are equivalent if they have the same truth values for all inputs. We write this as ≡.

Important equivalences (laws of logic):

Law	Expression
Double negation	¬¬P ≡ P
De Morgan’s Law 1	¬(P ∧ Q) ≡ ¬P ∨ ¬Q
De Morgan’s Law 2	¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Commutative (AND)	P ∧ Q ≡ Q ∧ P
Commutative (OR)	P ∨ Q ≡ Q ∨ P
Associative (AND)	(P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R)
Associative (OR)	(P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R)
Distributive 1	P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Distributive 2	P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

De Morgan’s Laws explained with a story:
“NOT (it is raining AND it is cold)” means the same as “it is NOT raining OR it is NOT cold.” If it’s not true that both are happening, then at least one is not happening.

2.5 Conditional Statements (If-Then)

The conditional P → Q (if P then Q) has several equivalent forms:

• Converse: Q → P (not logically equivalent to original)
• Inverse: ¬P → ¬Q (not logically equivalent to original)
• Contrapositive: ¬Q → ¬P (logically equivalent to original!)

Example:
Original: “If it is a dog, then it has fur.” (True? Not exactly – some dogs have hair, not fur, but let’s pretend)
Contrapositive: “If it does NOT have fur, then it is NOT a dog.” (Same meaning!)

Why contrapositive matters: Sometimes proving the contrapositive is easier than proving the original statement.

2.6 Predicates and Quantifiers (For All, There Exists)

A predicate is a statement that depends on a variable. For example, P(x) = “x is greater than 5”. This is not true or false until we know x.

Quantifiers tell us how many things satisfy a predicate.

Quantifier	Symbol	Meaning	Example
Universal (for all)	∀	All objects satisfy the predicate	∀x (x > 0) → “All numbers are greater than 0” (False)
Existential (there exists)	∃	At least one object satisfies the predicate	∃x (x > 100) → “There exists a number greater than 100” (True)

Example with real numbers:
Let P(x) = “x² = 4”.

• ∃x P(x) is true because x = 2 works.
• ∀x P(x) is false because not all numbers have square 4.

Negating quantifiers (important!):

• ¬∀x P(x) ≡ ∃x ¬P(x) (If it’s not true that all x satisfy P, then there exists some x that does NOT satisfy P)
• ¬∃x P(x) ≡ ∀x ¬P(x) (If there is no x that satisfies P, then all x do NOT satisfy P)

Example:
“Everyone in this room is wearing a hat.” To prove this is false, you only need to find ONE person without a hat (∃ person who is NOT wearing a hat).

Chapter 3: Set Theory – Groups of Things

Sets are the most basic way to group things in mathematics and computer science.

3.1 What is a Set?

A set is a collection of distinct objects. The objects are called elements or members.

Examples of sets:

• A = {1, 2, 3, 4, 5} (set of first five positive integers)
• B = {apple, banana, cherry} (set of fruits)
• C = {red, green, blue} (set of primary colors)
• D = {} (empty set, also written as ∅)

Important properties:

• Order does NOT matter: {1, 2, 3} is the same as {3, 2, 1}
• No duplicates: {1, 2, 2, 3} is just {1, 2, 3}

Notation:
x ∈ A means “x is an element of A” (example: 2 ∈ {1, 2, 3})
x ∉ A means “x is not an element of A” (example: 4 ∉ {1, 2, 3})

3.2 Ways to Describe a Set

Roster method: List all elements inside curly braces.
A = {1, 2, 3, 4, 5}

Set-builder notation: Describe the rule.
A = {x | x is an integer and 1 ≤ x ≤ 5}
Read as: “A is the set of all x such that x is an integer and x is between 1 and 5.”

Common sets you should know:

Symbol	Meaning
ℕ	Natural numbers {0, 1, 2, 3, …} (sometimes starting at 1)
ℤ	Integers {…, -2, -1, 0, 1, 2, …}
ℚ	Rational numbers (fractions)
ℝ	Real numbers (all numbers on the number line)
∅	Empty set

3.3 Subsets and Supersets

Subset (⊆): A is a subset of B if every element of A is also in B.
Example: {1, 2} ⊆ {1, 2, 3} (True)
Example: {1, 4} ⊆ {1, 2, 3} (False because 4 is not in B)

Proper subset (⊂): A is a proper subset of B if A ⊆ B and A ≠ B.
Example: {1, 2} ⊂ {1, 2, 3} (True)
Example: {1, 2, 3} ⊂ {1, 2, 3} (False – not proper because they are equal)

Superset (⊇): B is a superset of A if A ⊆ B.
Example: {1, 2, 3} ⊇ {1, 2}

Cardinality (size): |A| is the number of elements in A.
|{a, b, c}| = 3
|∅| = 0

3.4 Set Operations (Union, Intersection, Difference, Complement)

Let A and B be sets. The universal set U contains everything we care about.

Union (A ∪ B): All elements in A OR B (or both).
A ∪ B = {x | x ∈ A or x ∈ B}
Example: {1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}

Intersection (A ∩ B): Elements in both A AND B.
A ∩ B = {x | x ∈ A and x ∈ B}
Example: {1, 2, 3} ∩ {3, 4, 5} = {3}

Difference (A – B or A \ B): Elements in A but NOT in B.
A – B = {x | x ∈ A and x ∉ B}
Example: {1, 2, 3} – {3, 4, 5} = {1, 2}

Complement (Aᶜ or Ā): Elements NOT in A (within U).
Aᶜ = {x | x ∈ U and x ∉ A}
If U = {1, 2, 3, 4, 5} and A = {1, 2}, then Aᶜ = {3, 4, 5}

3.5 Venn Diagrams – Drawing Sets

Venn diagrams use circles to represent sets. The overlapping area is the intersection.

    +-------------------+
    |      U            |
    |   +---+   +---+   |
    |   | A |   | B |   |
    |   |   |   |   |   |
    |   +---+   +---+   |
    |                   |
    +-------------------+

• Left circle: Set A
• Right circle: Set B
• Overlap: A ∩ B
• Left-only: A – B
• Right-only: B – A
• Outside both: (A ∪ B)ᶜ

Venn diagram for three sets looks like three overlapping circles (like Olympic rings but all overlapping in the middle).

3.6 Cartesian Product

The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

Example:
A = {1, 2}, B = {x, y}
A × B = {(1, x), (1, y), (2, x), (2, y)}
|A × B| = |A| × |B| = 2 × 2 = 4

Example:
If you have 2 shirts (red, blue) and 3 pants (jeans, shorts, khakis), the Cartesian product gives all 2×3 = 6 outfits.

3.7 Power Set

The power set of A, written 𝒫(A) or 2ᴬ, is the set of all subsets of A (including the empty set and A itself).

Example:
A = {1, 2}
Subsets: ∅, {1}, {2}, {1, 2}
𝒫(A) = {∅, {1}, {2}, {1, 2}}
|𝒫(A)| = 2^{|A|} = 2² = 4

Example with 3 elements:
A = {a, b, c} has 2³ = 8 subsets.

Chapter 4: Functions – Mapping Inputs to Outputs

Functions are like machines: you put something in, and you get something out.

4.1 Definition of a Function

A function f from set A to set B (written f: A → B) assigns to each element a ∈ A exactly one element f(a) ∈ B.

• A is the domain (inputs)
• B is the codomain (possible outputs)
• The set of actual outputs is the range

Example:
f: {1, 2, 3} → {a, b, c} defined by f(1) = a, f(2) = b, f(3) = c

Not a function: If any input maps to two outputs, it’s not a function.

4.2 Domain, Codomain, and Range

Domain: All possible inputs.
Codomain: All possible outputs (some may never be used).
Range (image): The set of outputs that actually occur.

Example:
f(x) = x², with domain ℝ (all real numbers), codomain ℝ.
Range = {y | y ≥ 0} (non-negative numbers) because squares are never negative.

4.3 One-to-One (Injective) Functions

A function is one-to-one (injective) if different inputs always give different outputs.

Formally: If a₁ ≠ a₂, then f(a₁) ≠ f(a₂).

Example (injective): f(x) = 2x from ℝ to ℝ.
If 2a = 2b, then a = b. So it’s one-to-one.

Example (not injective): f(x) = x² from ℝ to ℝ.
f(2) = 4 and f(-2) = 4. Two inputs give the same output → not injective.

Example (injective):
Assigning each student a unique ID number. No two students share the same number.

4.4 Onto (Surjective) Functions

A function is onto (surjective) if every element in the codomain is used as an output.

Formally: For every b ∈ B, there exists some a ∈ A such that f(a) = b.

Example (onto): f(x) = x + 1 from ℝ to ℝ.
For any y, choose a = y – 1. Then f(a) = (y – 1) + 1 = y. So every output is reached.

Example (not onto): f(x) = x² from ℝ to ℝ.
Negative numbers like -1 are never outputs (since squares are ≥ 0). So not onto.

4.5 Bijective Functions

A function is bijective if it is both injective and surjective (one-to-one and onto).

A bijection creates a perfect pairing between A and B. |A| must equal |B|.

Example: f(x) = x + 5 from ℝ to ℝ.

• Injective? Yes.
• Surjective? Yes.
  So it is bijective.

Why bijections matter: A bijection has an inverse function.

4.6 Inverse Functions

If f: A → B is bijective, then there exists an inverse function f⁻¹: B → A such that f⁻¹(f(a)) = a and f(f⁻¹(b)) = b.

Example: f(x) = 2x + 3
To find inverse:

1. Write y = 2x + 3
2. Solve for x: y – 3 = 2x → x = (y – 3)/2
3. f⁻¹(y) = (y – 3)/2

Check: f⁻¹(f(x)) = ( (2x+3) – 3 )/2 = (2x)/2 = x ✅

4.7 Composition of Functions

Composition means applying one function, then another: (f ∘ g)(x) = f(g(x)).

Example:
f(x) = x², g(x) = x + 1
(f ∘ g)(x) = f(g(x)) = f(x + 1) = (x + 1)²
(g ∘ f)(x) = g(f(x)) = g(x²) = x² + 1

Note: Composition is not commutative: f ∘ g ≠ g ∘ f in general.

Chapter 5: Relations – Connecting Elements

5.1 What is a Relation?

A relation from set A to set B is a subset of A × B (the Cartesian product). It describes which elements are connected.

Example: A = {1, 2, 3}, B = {4, 5}
R = {(1,4), (1,5), (3,4)} means: 1 relates to 4 and 5, 2 relates to nothing, 3 relates to 4.

Binary relation on A: A relation from A to A (same set).
Example: “less than” on {1, 2, 3}: R = {(1,2), (1,3), (2,3)}

5.2 Properties of Relations (Reflexive, Symmetric, Transitive)

For a relation R on a set A:

Property	Definition	Example (on {1,2,3})
Reflexive	Every element relates to itself: (a,a) ∈ R for all a	{(1,1), (2,2), (3,3)}
Symmetric	If (a,b) ∈ R then (b,a) ∈ R	{(1,2), (2,1)}
Transitive	If (a,b) ∈ R and (b,c) ∈ R then (a,c) ∈ R	{(1,2), (2,3), (1,3)}

Example of “less than” on numbers:

• Reflexive? No (1 < 1 is false)
• Symmetric? No (1 < 2 does not imply 2 < 1)
• Transitive? Yes (if 1 < 2 and 2 < 3, then 1 < 3)

5.3 Equivalence Relations

An equivalence relation is a relation that is:

1. Reflexive
2. Symmetric
3. Transitive

Example 1: “Equals” (=) on numbers.

• Reflexive: a = a
• Symmetric: if a = b then b = a
• Transitive: if a = b and b = c then a = c

Example 2: “Same birthday as” on people.

• Reflexive: You have the same birthday as yourself.
• Symmetric: If I share birthday with you, you share with me.
• Transitive: If I share with you and you share with Alice, I share with Alice.

Equivalence classes: An equivalence relation splits the set into groups where all elements in a group are related to each other.

5.4 Partial Orders

A partial order is a relation that is:

1. Reflexive
2. Antisymmetric (if aRb and bRa then a = b)
3. Transitive

Example: “Less than or equal to” (≤) on numbers.

• Reflexive: a ≤ a
• Antisymmetric: if a ≤ b and b ≤ a then a = b
• Transitive: if a ≤ b and b ≤ c then a ≤ c

Example: Subset relation (⊆) on sets.

Chapter 6: Combinatorics – The Art of Counting

Combinatorics is about counting possibilities without listing them all.

6.1 The Basic Counting Principle

If you can do task A in m ways and task B in n ways, then you can do A and then B in m × n ways.

Example:
You have 3 shirts and 4 pants. How many outfits?
3 × 4 = 12 outfits.

Example with more steps:
Choosing a 3-digit code (digits 0-9, can repeat):
10 × 10 × 10 = 1000 possibilities.

6.2 Factorials – Multiplying Consecutive Numbers

Factorial (n!) means multiply all integers from 1 to n.

0! = 1 (by definition)
1! = 1
2! = 2 × 1 = 2
3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 120
6! = 720
10! = 3,628,800

Why factorials matter: They count the number of ways to arrange n distinct items.

6.3 Permutations – Arrangements Matter

A permutation is an ordered arrangement of items. Order matters.

Number of permutations of n distinct items: n!

Example: Arrange letters A, B, C.
ABC, ACB, BAC, BCA, CAB, CBA → 3! = 6 ways.

Permutations of r items from n:
P(n, r) = n! / (n – r)!

Example: How many ways to choose a president, vice-president, and secretary from 10 people?
P(10, 3) = 10! / 7! = 10 × 9 × 8 = 720 ways.

6.4 Combinations – Order Doesn’t Matter

A combination is a selection where order does NOT matter.

C(n, r) = n! / (r! × (n – r)!)

Example: Choose 3 students from 10 to be on a committee (no special roles).
C(10, 3) = 10! / (3! × 7!) = (10×9×8)/(3×2×1) = 720/6 = 120 ways.

Comparison:

• Permutation: picking winners (1st, 2nd, 3rd) → order matters.
• Combination: picking team members → order doesn’t matter.

6.5 Permutations with Repetition

If you have n items and you choose r of them with repetition allowed, the number of permutations is nʳ.

Example: How many 3-digit codes using digits 0-9?
10 × 10 × 10 = 10³ = 1000.

6.6 Combinations with Repetition

The number of ways to choose r items from n types with repetition allowed (order doesn’t matter) is:

C(n + r – 1, r)

Example: How many ways to choose 3 scoops of ice cream from 5 flavors (you can pick the same flavor multiple times)?
C(5 + 3 – 1, 3) = C(7, 3) = 7!/(3!4!) = 35 ways.

6.7 The Pigeonhole Principle

If you have n pigeons and m holes, and n > m, then at least one hole has at least two pigeons.

Simple statement: If you put more items than containers, some container must hold more than one.

Example 1: Among 13 people, at least 2 were born in the same month (12 months, 13 people → pigeonhole).

Example 2: In any group of 367 people, at least 2 share the same birthday (366 possible birthdays including leap day).

Advanced pigeonhole: If you put n items into k containers, some container has at least ⌈n/k⌉ items.

Chapter 7: Graph Theory – Dots and Lines

7.1 What is a Graph?

A graph G = (V, E) consists of:

• V (vertices or nodes): dots
• E (edges): lines connecting vertices

Example:
V = {A, B, C, D}
E = {{A,B}, {B,C}, {C,D}, {D,A}} (this forms a square).

7.2 Types of Graphs

Type	Description	Example
Undirected	Edges have no direction (go both ways)	Facebook friendships
Directed (Digraph)	Edges have arrows (one-way)	Twitter follows
Weighted	Edges have numbers (weights)	Road distances
Unweighted	All edges are equal	Simple connections
Simple	No loops (edge from vertex to itself) and no multiple edges	Most basic graphs
Complete (Kₙ)	Every vertex connects to every other	K₃ is a triangle

7.3 Degrees of Vertices

The degree of a vertex is the number of edges touching it.

In an undirected graph:
deg(A) = number of edges incident to A.

Example: In a triangle (3 vertices, each connected to the other two), each vertex has degree 2.

Handshaking Lemma: The sum of all degrees = 2 × (number of edges).
Because each edge contributes 2 to the sum of degrees.

In a directed graph:

• Indegree: number of edges coming IN
• Outdegree: number of edges going OUT
• Sum of indegrees = Sum of outdegrees = number of edges

7.4 Paths, Cycles, and Connectivity

Walk: A sequence of vertices where consecutive vertices are connected by edges.
Path: A walk with no repeated vertices.
Cycle: A path that starts and ends at the same vertex, with no other repeats.

Connected graph: There is a path between every pair of vertices.
Disconnected graph: The graph has separate pieces (components).

7.5 Eulerian and Hamiltonian Paths

Eulerian path: A path that uses every edge exactly once.
Eulerian circuit: An Eulerian path that starts and ends at the same vertex.

Condition for Eulerian circuit (undirected graph):

• The graph is connected.
• Every vertex has even degree.

Condition for Eulerian path (not circuit):

• Exactly 0 or 2 vertices have odd degree.

Hamiltonian path: A path that visits every vertex exactly once.
Hamiltonian cycle: A Hamiltonian path that returns to the start.

Note: There is no simple rule for Hamiltonian paths (it’s a hard problem).

7.6 Graph Coloring

Graph coloring means assigning colors to vertices so that no two adjacent vertices share the same color.

Chromatic number: The minimum number of colors needed.

Example:

• A triangle (K₃) needs 3 colors.
• A bipartite graph (two sets with no edges inside each set) needs 2 colors.
• A tree (no cycles) needs 2 colors.

Four Color Theorem: Any map (planar graph) can be colored with 4 colors.

7.7 Shortest Path Algorithms (Dijkstra’s Algorithm)

Dijkstra’s algorithm finds the shortest path from a start vertex to all others in a weighted graph (all weights non-negative).

Steps:

1. Set distance to start = 0, all others = infinity.
2. Mark all vertices unvisited.
3. While unvisited vertices remain:

• Pick unvisited vertex with smallest distance.
• For each neighbor, calculate new distance = current distance + edge weight.
• If new distance < neighbor’s current distance, update it.
• Mark current vertex as visited.

Example: Finding the shortest route from home to school on a map.

Chapter 8: Trees – A Special Kind of Graph

8.1 Definition and Properties

A tree is a connected graph with no cycles.

Properties of a tree with n vertices:

• Has exactly n – 1 edges.
• There is exactly one path between any two vertices.
• Removing any edge disconnects the graph.

Examples: Family tree, file system directories, organization chart.

8.2 Rooted Trees

A rooted tree has one vertex designated as the root.

• Parent: Vertex above another.
• Child: Vertex below another.
• Leaf: Vertex with no children.
• Internal vertex: Not a leaf (has at least one child).

8.3 Binary Trees

A binary tree is a rooted tree where each node has at most 2 children (left and right).

Types:

• Full binary tree: Every node has 0 or 2 children.
• Complete binary tree: All levels filled except possibly last, and last level has leftmost nodes.
• Perfect binary tree: All internal nodes have 2 children and all leaves at same level.

8.4 Tree Traversals (Preorder, Inorder, Postorder)

Visiting all nodes in a binary tree in different orders:

Traversal	Order	Example on tree: root(10), left(5), right(15)
Preorder	Root → Left → Right	10, 5, 15
Inorder	Left → Root → Right	5, 10, 15
Postorder	Left → Right → Root	5, 15, 10

Python-like code for inorder:

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value)
        inorder(node.right)

8.5 Spanning Trees

A spanning tree of a connected graph G is a subgraph that is a tree and includes all vertices of G.

Properties:

• Has exactly |V| – 1 edges.
• A graph can have many spanning trees.

8.6 Minimum Spanning Trees (Kruskal’s and Prim’s Algorithms)

A minimum spanning tree (MST) is a spanning tree with the smallest possible total edge weight.

Kruskal’s Algorithm:

1. Sort all edges by weight (smallest to largest).
2. Add edges one by one, skipping any that would create a cycle.
3. Stop when you have |V| – 1 edges.

Prim’s Algorithm:

1. Start with one vertex.
2. Repeatedly add the smallest edge connecting the current tree to a new vertex.
3. Stop when all vertices are included.

Use case: Designing the cheapest road network to connect all cities.

Chapter 9: Recurrence Relations – Solving Problems Step by Step

9.1 What is a Recurrence Relation?

A recurrence relation defines a sequence where each term is a function of previous terms. It also needs base cases (starting values).

Form: aₙ = f(aₙ₋₁, aₙ₋₂, …, aₙ₋ₖ)

9.2 Fibonacci Sequence

The most famous recurrence:
F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Example: Rabbit population problem – each pair produces a new pair every month.

9.3 Solving Linear Recurrences

A linear homogeneous recurrence with constant coefficients:
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ + … + cₖaₙ₋ₖ

Solution steps:

1. Write characteristic equation: rᵏ = c₁rᵏ⁻¹ + c₂rᵏ⁻² + … + cₖ
2. Solve for r.
3. General form: aₙ = A₁r₁ⁿ + A₂r₂ⁿ + …
4. Use base cases to find constants.

Example: Fibonacci: r² = r + 1 → r² – r – 1 = 0 → r = (1 ± √5)/2
aₙ = A((1+√5)/2)ⁿ + B((1-√5)/2)ⁿ

9.4 Master Theorem for Divide-and-Conquer

For recurrences of the form: T(n) = a T(n/b) + f(n)

Case 1: If f(n) = O(n^{log_b a – ε}), then T(n) = Θ(n^{log_b a})
Case 2: If f(n) = Θ(n^{log_b a}), then T(n) = Θ(n^{log_b a} log n)
Case 3: If f(n) = Ω(n^{log_b a + ε}) and af(n/b) ≤ cf(n), then T(n) = Θ(f(n))

Example: Merge Sort: T(n) = 2T(n/2) + O(n) → a=2, b=2, log_b a = 1, f(n)=n → Case 2 → T(n) = Θ(n log n)

Chapter 10: Proof Techniques – How to Be Certain

10.1 Direct Proof

Assume the hypothesis is true, then use logical steps to show the conclusion is true.

Example: Prove “If n is even, then n² is even.”
Proof: n = 2k → n² = (2k)² = 4k² = 2(2k²) → even.

10.2 Proof by Contradiction

Assume the opposite of what you want to prove, then derive a contradiction.

Example: Prove √2 is irrational.
Assume √2 = a/b in lowest terms. Then 2 = a²/b² → 2b² = a² → a is even → a=2k → 2b² = 4k² → b²=2k² → b is even. Then a and b both even, contradicting “lowest terms.”

10.3 Proof by Induction

Used for statements about natural numbers.

Steps:

1. Base case: Prove for n = 1 (or smallest value).
2. Inductive step: Assume true for n = k, prove for n = k+1.

Example: Prove 1 + 2 + … + n = n(n+1)/2
Base: n=1, LHS=1, RHS=1×2/2=1 ✅
Inductive: Assume true for k. Then for k+1:
1+…+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k/2 + 1) = (k+1)(k+2)/2 ✅

10.4 Proof by Contrapositive

Prove P → Q by proving ¬Q → ¬P.

Example: Prove “If n² is odd, then n is odd.”
Contrapositive: “If n is even, then n² is even.” (Easier to prove!)
n=2k → n²=4k²=2(2k²) → even ✅

Chapter 11: Conclusion – Why Discrete Math Matters for Your Future

We have covered a vast landscape:

• Logic teaches you to think clearly and avoid mistakes.
• Set theory is the language of databases and collections.
• Functions are the foundation of programming (input → output).
• Relations model connections in social networks and databases.
• Combinatorics helps you count possibilities (passwords, probabilities).
• Graph theory powers GPS navigation, social media, and network routing.
• Trees organize file systems, HTML documents, and game decision trees.
• Recurrences analyze algorithm speed (like Merge Sort).
• Proofs give you confidence that your code works correctly.

Every programmer uses discrete math daily – often without realizing it. When you write an if-statement, you use logic. When you store data in a dictionary, you use hash tables (which rely on modular arithmetic). When you navigate a tree structure, you use graph theory.

Keep practicing!

• Solve problems on platforms like Brilliant.org or Khan Academy.
• Draw Venn diagrams and truth tables by hand.
• Try proving simple statements about numbers.
• Build small graphs for your favorite social network.

Discrete math is not just a subject to pass – it is a way of thinking that will make you a better problem solver, programmer, and logical thinker for life.