1. Why Start Here?
The Historical Origin: The Seven Bridges of Königsberg (1736)
In the 18th century, the city of Königsberg, Prussia (now Kaliningrad, Russia), was set on both sides of the Pregel River and included two large islands. The islands and mainland were connected by seven bridges. A popular puzzle among the townspeople was: Can you take a walk through the city in such a way that you cross each of the seven bridges exactly once and return to where you started?
Leonhard Euler's Breakthrough Solution
In 1736, the Swiss mathematician Leonhard Euler realized that the geographical maps, landmass sizes, and exact lengths of the bridges were completely irrelevant. What mattered was pure connectivity. Euler abstracted the landmasses as distinct points (which we now call vertices or nodes) and the bridges connecting them as lines (which we now call edges or links).
Euler proved mathematically that such a walk was impossible. In doing so, he invented both Graph Theory and the mathematical discipline of Topology. His key insight was rooted in counting degrees of connections: every time you visit a landmass, you must enter via one bridge and leave via another. Therefore, every landmass must have an even number of bridges attached to it if you want to enter and leave without getting stuck. Since all four landmasses in Königsberg had an odd number of bridges attached (3, 3, 3, and 5), the path was impossible.
What Exactly Is a Graph?
To study graphs rigorously without relying on hand-drawn pictures, we need a precise mathematical definition. A graph \(G\) is a pair of sets:
$$G = (V, E)$$
- \(V\) is a non-empty set of elements called vertices (or nodes).
- \(E\) is a set of edges (or links), where each edge connects a pair of vertices.
For instance, in a simple social network graph:
• \(V = \{\text{Alice}, \text{Bob}, \text{Charlie}\}\)
• \(E = \{\{\text{Alice}, \text{Bob}\}, \{\text{Bob}, \text{Charlie}\}\}\)
This simple definition rests entirely on set theory. To understand graph theorems, analyze algorithms, and write formal proofs, we must first master the discrete-math engine under the hood.
Key Insight
Almost every graph-theory proof reduces to one of four core strategies: direct construction/computation, induction on the number of vertices or edges, contradiction using structural properties, or minimal counterexample arguments. Mastering these logic tools enables you to read, prove, and apply any graph algorithm effortlessly.
2. Sets, Relations & Functions
Sets and Set Operations
Think of a set as a unique digital container or database table containing distinct items where order does not matter. We denote a set using curly braces: \(A = \{1, 2, 3\}\). We write \(a \in A\) to mean "\(a\) is an element of \(A\)," and \(B \subseteq A\) to state that \(B\) is a subset of \(A\) (every element in \(B\) is also inside \(A\)).
Real-World Analogy: Imagine a database of online users. Let Set \(A\) be users who bought a laptop, and Set \(B\) be users who bought wireless headphones.
| Operation | Notation | Real-World Meaning | Graph-Theory Application |
|---|---|---|---|
| Union | \(A \cup B\) | Users who bought a laptop OR headphones (or both). | Combining vertex sets or merging subgraphs. |
| Intersection | \(A \cap B\) | Users who bought BOTH a laptop and headphones. | Finding common mutual friends or shared network nodes. |
| Difference | \(A \setminus B\) | Users who bought a laptop but NOT headphones. | Deleting vertices or removing edges from a graph. |
| Complement | \(A^c\) or \(\overline{A}\) | All users in the system who did NOT buy a laptop. | Constructing complement graphs (non-connected edges). |
| Cartesian Product | \(A \times B\) | All possible pairs combining one element from \(A\) and one from \(B\). | Defining directed edges between two clusters of vertices. |
flowchart LR
subgraph Universal_Set ["System Users Universe"]
A(("Set A: Laptop Buyers"))
B(("Set B: Headphone Buyers"))
end
A -- "Union (A ∪ B)" --> C["A ∪ B: All unique buyers"]
A -- "Intersection (A ∩ B)" --> D["A ∩ B: Mutual buyers only"]
B -- "Complement (Aᶜ)" --> E["Aᶜ: Non-laptop buyers"]
Relations and Equivalence Classes
A relation \(R\) between set \(A\) and set \(B\) is simply a collection of ordered pairs taking elements from \(A \times B\). When \(A = B\), we say \(R\) is a relation on \(A\). If \((a, b) \in R\), we write \(a \mathrel{R} b\).
In graph theory, adjacency is a binary relation: vertex \(u\) is related to vertex \(v\) if an edge connects them.
A relation \(R\) on a set \(A\) is called an Equivalence Relation if it satisfies three strict properties:
- Reflexive: Every element is related to itself (\(a \mathrel{R} a\)).
- Symmetric: If \(a \mathrel{R} b\), then \(b \mathrel{R} a\).
- Transitive: If \(a \mathrel{R} b\) and \(b \mathrel{R} c\), then \(a \mathrel{R} c\).
Real-World Application: Social Networks & Connected Components
Consider a social media platform like LinkedIn. Define a relation \(\sim\) on the set of user accounts where \(u \sim v\) if user \(u\) can send a direct message to user \(v\) through a chain of connections.
• Reflexivity: You can message yourself (\(u \sim u\)).
• Symmetry: If you can message user \(v\), then user \(v\) can message you back (\(u \sim v \implies v \sim u\)).
• Transitivity: If you can message \(v\) and \(v\) can message \(w\), then a routing path exists from you to \(w\) (\(u \sim v \text{ and } v \sim w \implies u \sim w\)).
Because \(\sim\) is an equivalence relation, it cleanly partitions the entire user base into isolated, non-overlapping groups called Equivalence Classes. In graph theory, these equivalence classes are known as Connected Components.
Functions: Injections, Surjections & Bijections
A function \(f: A \to B\) is a rule that assigns exactly one element in set \(B\) (the codomain) to each element in set \(A\) (the domain).
Analogy: Think of set \(A\) as students in a classroom and set \(B\) as exam scores (0 to 100).
- Injective (One-to-One): No two distinct students receive the exact same score. If \(f(a_1) = f(a_2)\), then \(a_1 = a_2\).
- Surjective (Onto): Every possible score from 0 to 100 was achieved by at least one student. The range equals the codomain.
- Bijective (One-to-One Correspondence): The function is both injective and surjective. Each student has a unique score, and every possible score is claimed. A bijection means set \(A\) and set \(B\) have the exact same size (\(|A| = |B|\)).
Case Study: Graph Isomorphism via Bijections
How do computer software algorithms check if two network topologies are identical even if their visual layouts look totally different? They search for a Graph Isomorphism.
Two graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are isomorphic if there exists a bijection \(f: V_1 \to V_2\) such that two vertices \(u, v \in V_1\) share an edge in \(G_1\) if and only if \(f(u)\) and \(f(v)\) share an edge in \(G_2\).
3. Logic, Predicates & Quantifiers
Propositions and Truth Tables
A proposition is a mathematical statement that is unambiguously either True (\(T\)) or False (\(F\)). We combine simple propositions using logical operators:
| \(P\) | \(Q\) | AND (\(P \land Q\)) | OR (\(P \lor Q\)) | IMPLIES (\(P \implies Q\)) | IFF (\(P \iff Q\)) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | F | F |
| F | T | F | T | T | F |
| F | F | F | F | T | T |
Common Pitfall: Logical Implication (\(P \implies Q\))
Notice in the truth table that when \(P\) is False, the implication \(P \implies Q\) is automatically evaluated as True (vacuously true). For example: "If pigs can fly, then 2 + 2 = 5" is a logically true mathematical statement because the premise is false!
Quantifiers (\(\forall, \exists\)) and Negation
In graph theory, theorems make assertions about sets of elements using quantifiers:
- Universal Quantifier (\(\forall\)): "For all" or "For every".
Example: \(\forall v \in V, \deg(v) \geq 1\) means "Every vertex in the graph has at least one edge." - Existential Quantifier (\(\exists\)): "There exists at least one".
Example: \(\exists v \in V \text{ such that } \deg(v) = 0\) means "There exists an isolated vertex with no edges."
To negate a quantified logical statement, follow De Morgan's Rules for Quantifiers: swap the quantifier and negate the internal statement.
$$\neg \big( \forall x, P(x) \big) \equiv \exists x, \neg P(x)$$
$$\neg \big( \exists x, P(x) \big) \equiv \forall x, \neg P(x)$$
Real Application: Negating Network Connectivity
Definition of Connected Graph: \(\forall u, v \in V\), there exists a path between \(u\) and \(v\).
Negation (Disconnected Graph): \(\exists u, v \in V\) such that for all potential paths, \(u\) and \(v\) are not connected. This precise logical structure tells you exactly what to prove when establishing that a network is disconnected!
4. The Master Toolset of Mathematical Proofs
Direct Proof and Contrapositive
To prove an implication \(P \implies Q\):
- Direct Proof: Assume \(P\) is true, apply known definitions/rules, and directly deduce that \(Q\) must be true.
- Proof by Contrapositive: Prove the logically equivalent statement \(\neg Q \implies \neg P\). Assume \(Q\) is false and prove that \(P\) must be false.
Contrapositive Proof: Cut-Edges in Trees
Claim: If a connected graph \(G\) contains no cycles, then removing any edge \(e\) disconnects \(G\).
Proof via Contrapositive (\(\neg Q \implies \neg P\)): Assume that removing edge \(e = (u, v)\) does NOT disconnect \(G\). That means there still exists a path connecting \(u\) and \(v\) in \(G \setminus \{e\}\). But if a path already exists between \(u\) and \(v\) without using edge \(e\), then adding edge \(e\) back creates a closed loop (a cycle). Thus, \(G\) contains a cycle. We proved \(\neg Q \implies \neg P\), which proves the original claim!
Proof by Contradiction
To prove a claim \(P\), assume its negation \(\neg P\) is true. Work step-by-step through logical deductions until you reach an impossible absurdity (e.g., \(1 = 0\), or a node being simultaneously even and odd). This forces \(\neg P\) to be false, proving \(P\) is true.
Classic Proof: The Handshaking Lemma Parity
Theorem: In any finite undirected graph, the number of vertices with an odd degree is always even.
Proof: The degree of a vertex \(\deg(v)\) is the number of edges touching it. Summing the degrees of all vertices counts every edge twice (once from each endpoint):
$$\sum_{v \in V} \deg(v) = 2|E|$$
The sum of all degrees is always an even number because it equals \(2|E|\). Now, split the vertex set \(V\) into two groups: \(V_{even}\) (vertices with even degrees) and \(V_{odd}\) (vertices with odd degrees):
$$\sum_{v \in V_{even}} \deg(v) + \sum_{v \in V_{odd}} \deg(v) = 2|E|$$
The sum over \(V_{even}\) is even. Subtracting it from the even total \(2|E|\) implies that \(\sum_{v \in V_{odd}} \deg(v)\) must also be even.
Suppose for contradiction that the number of odd-degree vertices \(|V_{odd}|\) were odd. Adding up an odd count of odd numbers always yields an odd total. But we just showed the sum must be even! This contradiction proves that \(|V_{odd}|\) must be even.
Mathematical and Strong Induction
Mathematical Induction proves that a statement \(P(n)\) holds for all integers \(n \geq n_0\):
- Base Case: Show that \(P(n_0)\) is true.
- Inductive Step: Assume \(P(k)\) is true (the Inductive Hypothesis) for an arbitrary integer \(k \geq n_0\), and prove that \(P(k+1)\) must also be true.
Strong Induction allows you to assume that \(P(m)\) is true for all integers \(m\) from \(n_0\) up to \(k\), which is essential when breaking graphs down into multiple smaller subgraphs.
Proving Tree Edges via Induction: \(|E| = |V| - 1\)
A tree is a connected graph with no cycles. Let's prove that every tree with \(n\) vertices has exactly \(n - 1\) edges.
Base Case (\(n = 1\)): A tree with 1 vertex has 0 edges. \(1 - 1 = 0\). \(\checkmark\)
Inductive Step: Assume every tree with \(k\) vertices has \(k - 1\) edges. Let \(T\) be a tree with \(k + 1\) vertices. Every finite tree with \(k+1 \geq 2\) vertices possesses at least one leaf (a vertex of degree 1). Remove this leaf vertex and its single attached edge. The remaining graph \(T'\) is still connected and acyclic, with \(k\) vertices. By our inductive hypothesis, \(T'\) has \(k - 1\) edges. Reattaching the leaf adds 1 vertex and 1 edge back, yielding \((k - 1) + 1 = k\) edges for \(k + 1\) vertices. \(\checkmark\)
Below is an executable Python script that generates random trees using Prüfer Sequences and computationally verifies this fundamental \(n-1\) edge property across graph sizes:
import random
def generate_random_tree(n):
"""
Generates a random tree with n vertices using Prüfer sequences.
Returns the edge list of the tree.
"""
if n == 1:
return []
if n == 2:
return [(0, 1)]
# Generate random Prüfer sequence of length n-2
prufer = [random.randint(0, n - 1) for _ in range(n - 2)]
degree = [1] * n
for node in prufer:
degree[node] += 1
edges = []
for node in prufer:
for v in range(n):
if degree[v] == 1:
edges.append((v, node))
degree[v] -= 1
degree[node] -= 1
break
# Connect last two remaining vertices
last = [v for v in range(n) if degree[v] == 1]
edges.append((last[0], last[1]))
return edges
# Empirical Verification of Theorem: |E| = |V| - 1
test_sizes = [1, 2, 5, 10, 50, 100, 500]
print("Testing Tree Edge Theorem (|E| = |V| - 1):")
for n in test_sizes:
edges = generate_random_tree(n)
num_edges = len(edges)
assert num_edges == n - 1, f"Failed for n={n}"
print(f"Vertices (|V|): {n:>3} | Edges (|E|): {num_edges:>3} | Formula (n-1): {n-1:>3} -> PASSED")
Minimal Counterexample Strategy
The Minimal Counterexample technique combines proof by contradiction with the Well-Ordering Principle (which states that every non-empty set of non-negative integers contains a smallest element):
- Assume the theorem is false.
- Choose the smallest possible counterexample (e.g., a graph with the minimum number of vertices \( |V| = n^* \)).
- Perform an operation on this minimal counterexample to construct an even smaller instance \(n < n^*\).
- Show that this smaller instance must also fail the theorem.
- This contradicts the assumption that \(n^*\) was the minimal counterexample!
5. Hands-On Exercises & Solutions
Exercise 1 (Functions & Injections): Let \(f: A \to B\) and \(g: B \to C\) be injective functions. Prove directly that their composition \((g \circ f): A \to C\) is also injective.
Exercise 2 (Mathematical Logic): Write down the formal negation of the following graph-theory claim: "For every graph \(G\), if \(G\) has 6 vertices, then \(G\) contains a triangle (cycle of length 3) or an independent set of size 3."
Exercise 3 (Proof by Contradiction): Prove that in any group of 2 or more people, there are at least two people who have the exact same number of friends within the group (assuming friendship is mutual).
Click to View Solutions
Solution 1: To show \((g \circ f)(a_1) = (g \circ f)(a_2) \implies a_1 = a_2\).
1. Assume \((g \circ f)(a_1) = (g \circ f)(a_2)\), which means \(g(f(a_1)) = g(f(a_2))\).
2. Since \(g\) is injective, \(g(x) = g(y) \implies x = y\). Thus \(f(a_1) = f(a_2)\).
3. Since \(f\) is injective, \(f(a_1) = f(a_2) \implies a_1 = a_2\). \(\blacksquare\)
Solution 2: Negating \(\forall G (P(G) \implies Q(G))\) yields \(\exists G (P(G) \land \neg Q(G))\).
"There exists at least one graph \(G\) with 6 vertices that contains NEITHER a triangle NOR an independent set of size 3."
Solution 3: Let \(n \ge 2\) be the number of people (vertices). Possible friend counts (degrees) range from \(0\) to \(n-1\). However, it is impossible to simultaneously have a person with \(0\) friends (isolated node) and a person with \(n-1\) friends (connected to everyone). Thus, there are only \(n-1\) possible friend counts available for \(n\) people. By the Pigeonhole Principle, at least two people must share the exact same number of friends. \(\blacksquare\)
6. Conclusion & Next Steps
You now possess the foundational bedrock of discrete mathematics: set operations, equivalence relations, functions, logical quantifiers, and the major proof paradigms (direct, contrapositive, contradiction, induction, and minimal counterexample). Every concept introduced here will be used directly throughout the rest of this graph theory series.
Next in the Series
In Part 2: Combinatorics, Probability & Algorithm Complexity, we expand our toolset with counting techniques (Pigeonhole Principle, double counting), probability basics for random graphs, and Big-O notation for algorithmic complexity.