Rosen · Discrete Mathematics · Chapter 10

Graph Theory

Every concept. Every type. Every theorem. All interactive — touch, click, drag, simulate.

10.1

Graphs and Graph Models

Graphs model pairwise relationships. Six model types depending on direction, loops, and multi-edges.

◈
Simple Graph Model 1
Definition
G=(V,E) where V=vertices, E=set of unordered pairs {u,v}. No loops, no parallel edges.

Most common model. Used for symmetric, unique relationships.

Real-World
Friend networks — two people either friends or not, can't be double-friends, can't friend themselves.
|E| ≤ C(|V|,2) = |V|(|V|−1)/2

Build your own: Click canvas to add nodes. Click two nodes to add edge.

// Simple Graph Builder
Add Node Add Edge Clear
Click canvas to place vertices
Nodes: 0 | Edges: 0 | Max possible: 0
⧫
Multigraph & Pseudograph Model 2 & 3
Multigraph
Allows multiple parallel edges between same vertex pair. No loops.
Pseudograph
Allows both parallel edges AND loops (edge from v to itself).
Examples
Multigraph: Airlines — multiple flights between two cities.
Pseudograph: Web graph — page can link to itself.

A loop contributes 2 to the degree of its vertex.

// Multigraph & Loop Demo
Node Edge Loop Clear
Add nodes, parallel edges, or loops
Loops: 0 | Multi-edges: 0
→
Directed Graph (Digraph) Model 4 & 5
Digraph
Edges are ordered pairs (u,v) — direction matters. (u,v) ≠ (v,u).
In/Out Degree
in-deg(v) = edges INTO v | out-deg(v) = edges OUT OF v
∑in-deg = ∑out-deg = |E|
Examples
Web graph: hyperlinks are directed. Twitter follows: A follows B ≠ B follows A. Task dependencies: A must finish before B.
// Digraph Builder · arrows show direction
Node Arc Clear
Build directed graph
in-deg and out-deg shown beside each node
10.2

Graph Terminology

Adjacency, degree, paths, circuits — the vocabulary of graph theory.

∑
Degree & Handshaking Lemma Theorem 1
Degree deg(v)
Number of edges incident to v. Loop counts twice.
Handshaking Lemma
For any undirected graph:
∑ deg(v) = 2|E|
Corollary
Every graph has an even number of odd-degree vertices.
Why?
Each edge contributes exactly 2 to the total degree sum (one to each endpoint). So sum always even.

Isolated vertex: deg=0. Pendant: deg=1.

// Handshaking Verifier · hover nodes · add edges
Node Edge Clear Random
Hover nodes to see degree
∑deg = 0 | 2|E| = 0 | Odd-deg nodes: 0 | Lemma holds: —
⟿
Paths, Circuits, Cycles Definitions
Walk
Sequence v₀,e₁,v₁,…,eₙ,vₙ. Edges/vertices may repeat.
Trail
Walk where no edge repeats.
Path
Walk where no vertex repeats. Length = number of edges.
Circuit / Closed Walk
Walk that starts and ends at same vertex.
Cycle
Closed path — no repeated vertices except start=end.
Key Fact
If path exists from u to v, a simple path (no repeated vertices) also exists.
// Path Explorer · click nodes to trace path
New Graph Clear Path
Click nodes in sequence to trace a path
Path: — | Length: 0 | Type: —
10.2b

Special Types of Graphs

K
Complete Graph Kₙ Special Type 1
Definition
Every pair of distinct vertices connected by exactly one edge. Fully dense.
|E| = n(n−1)/2  |  deg(v) = n−1 for all v
Values
K₁: 0 edges | K₂: 1 | K₃: 3 | K₄: 6 | K₅: 10 | K₆: 15
Key Property
K₁,K₂,K₃,K₄ are planar. K₅ is NOT planar.

χ(Kₙ) = n. Maximum chromatic number for n vertices.

// Complete Graph Kₙ · drag slider
Vertices: 5 | Edges: 10 | Each degree: 4 | Planar: No (K₅)
○
Cycle Graph Cₙ & Wheel Wₙ Special Type 2
Cycle Cₙ
n vertices in a ring. Each vertex has degree 2. Minimum n=3.
Cₙ: |E|=n, all deg=2 | χ = 2 if n even, 3 if n odd
Wheel Wₙ
Cₙ plus one hub vertex connected to all rim vertices.
Wₙ: |V|=n+1, |E|=2n | Hub deg=n, Rim deg=3
Bipartite check
Cₙ bipartite iff n is even (alternating 2-coloring works).
// Cycle & Wheel · toggle type · adjust n
Cycle Cₙ Wheel Wₙ
Cycle C₆: V=6, E=6, χ=2 (even → bipartite)
⊕
Bipartite Graph & Kₘ,ₙ Special Type 3
Bipartite
V splits into two disjoint sets V₁,V₂. Every edge goes between V₁ and V₂. No edges within same set.
Characterization Theorem
G is bipartite ⟺ G contains no odd-length cycle.
Complete Bipartite Kₘ,ₙ
Every vertex in V₁ connected to every vertex in V₂.
|E| = m·n  |  deg in V₁ = n  |  deg in V₂ = m
Example
Job assignment: workers (V₁) → jobs (V₂). K₃,₃ is not planar.
// Bipartite Builder · 2-color check · BFS detection
V₁ Node V₂ Node Edge Check Bipartite Clear
Add nodes to V₁ or V₂, then edges between them
Is bipartite: —
Q
Hypercube Graph Qₙ Special Type 4
Hypercube Qₙ
Vertices = all n-bit binary strings. Edge between two strings differing in exactly 1 bit (Hamming distance 1).
|V| = 2ⁿ  |  |E| = n·2ⁿ⁻¹  |  deg(v) = n (n-regular)
Q₃ Example
000–001–011–010 (change bit 0, 1, 0). Used in parallel computer interconnects, Gray codes.
Properties
Qₙ is bipartite (0-weight vs 1-weight strings). Has Hamiltonian circuit. χ(Qₙ)=2.
// Hypercube Q₁, Q₂, Q₃ · click edge to highlight path
Q₁ Q₂ Q₃
Q₁: 2 vertices, 1 edge
P
Petersen Graph Famous Graph
Petersen Graph
10 vertices, 15 edges, 3-regular. Outer 5-cycle + inner 5-cycle (pentagram) + spokes.
Properties
NOT planar. χ=3. No Hamiltonian circuit. Girth=5 (shortest cycle length). Famous counterexample in many graph theory conjectures.
Why Famous?
Appears as minimal counterexample in dozens of theorems about cubic graphs, planarity, coloring, and matchings.
// Petersen Graph · drag nodes · 3-coloring shown
Show 3-Coloring Reset
V=10 | E=15 | 3-regular | χ=3 | Not planar | No Hamilton circuit
10.3a

Representing Graphs

[]
Adjacency Matrix, Incidence Matrix & Adjacency List Data Structures
Adjacency Matrix
n×n matrix A. A[i][j]=1 if edge {i,j} exists.
Space: O(V²). Fast edge lookup O(1).
Key
Symmetric for undirected. Diagonal=0 for simple. Row sum = deg(vᵢ).
Incidence Matrix
n×m matrix M. M[i][j]=1 if vᵢ incident to eⱼ.
Space: O(V·E). Col sum always=2.
Key
Good for edge-centric operations. Row sum = degree.
Adjacency List
Array of lists: adj[v] = neighbors of v.
Space: O(V+E). Best for sparse graphs.
Key
Default for most algorithms. Traversal: O(V+E).
// Live Representation · build graph · all three views update instantly
Node Edge Clear Sample
Adjacency Matrix
Incidence Matrix
Adjacency List
10.3b

Graph Isomorphism

≅
Isomorphism & Invariants Structural Equivalence
Isomorphism
G₁≅G₂ if bijection f:V₁→V₂ exists where {u,v}∈E₁ ⟺ {f(u),f(v)}∈E₂. Same graph, different labels.
Invariants — Necessary but NOT Sufficient
Same |V| · Same |E| · Same degree sequence · Same # cycles · Same girth · Same # connected components
Strategy
To prove NOT isomorphic: find one invariant that differs. To prove IS isomorphic: exhibit explicit bijection.
Hard Problem
Graph Isomorphism is in NP but not known to be in P or NP-complete. One of CS theory's great open questions.
// Isomorphism Checker · generate pairs · compare invariants
GRAPH G₁
GRAPH G₂
Generate Isomorphic Pair Generate Non-Isomorphic Compare Invariants
Click a button to generate graph pairs
10.4

Connectivity

⬡
Connected Graphs & Components Connectivity 1
Connected
Undirected graph where path exists between every pair of vertices.
Connected Component
Maximal connected subgraph. Disconnected graph = union of components.
Strongly Connected (Digraph)
∀u,v: path u→v AND v→u both exist.
Weakly Connected
Underlying undirected graph is connected.
Theorem
Complete graph Kₙ: removing any k ≤ n−2 vertices still connected. κ(Kₙ)=n−1.
// Component Finder · BFS colors each component
Node Edge Find Components Clear Random
Build graph then Find Components
Components: — | Connected: —
↻
BFS & DFS Traversal Connectivity 2
BFS — Breadth-First Search
Visit all neighbors before going deeper. Uses queue. Finds shortest paths (unweighted). Explores level by level.
Time: O(V+E) | Space: O(V)
DFS — Depth-First Search
Go as deep as possible before backtracking. Uses stack (or recursion). Detects cycles, topological sort, SCC.
Time: O(V+E) | Space: O(V)
BFS Tree
BFS on connected G produces spanning tree. Tree edges = shortest paths from source.
// BFS vs DFS · watch them explore differently
▶ Run BFS ▶ Run DFS Step Reset New Graph
Click Run BFS or DFS to begin
Source
In Queue/Stack
Visited
Unvisited
Visit order: —
✂
Cut Vertices & Bridges Connectivity 3
Cut Vertex (Articulation Point)
Vertex whose removal increases the number of connected components. Critical node in network.
Bridge
Edge whose removal disconnects the graph. Single point of failure in network.
Tarjan's Algorithm
Finds all cut vertices and bridges in O(V+E) using DFS timestamps and low-link values.
Application
Network design: avoid bridges and cut vertices for fault tolerance. Routers, power grids, supply chains.
// Cut Vertex & Bridge Finder · Tarjan's algorithm
Find Cut Vertices Find Bridges Reset New Graph
Cut Vertex
Bridge
Click Find Cut Vertices or Find Bridges
κ
κ(G) and λ(G) — Connectivity Numbers Connectivity 4
Vertex Connectivity κ(G)
Min # vertices to remove to disconnect G. Measures vertex robustness.
Edge Connectivity λ(G)
Min # edges to remove to disconnect G. Measures edge robustness.
Whitney's Inequality
κ(G) ≤ λ(G) ≤ δ(G) where δ = minimum degree
Examples
Tree: κ=1 (any leaf neighbor), λ=1 (any edge is bridge)
Kₙ: κ=λ=n−1 (most robust)
Cycle Cₙ: κ=λ=2
// Connectivity Calculator · shows κ and λ
Node Edge Calculate κ, λ, δ Clear Sample Graph
κ(G) = — | λ(G) = — | δ(G) = — | κ ≤ λ ≤ δ: —
10.5a

Euler Paths & Circuits

∀
Euler Circuit — All Edges Once Euler 1
Euler Circuit
Circuit traversing every edge exactly once. May revisit vertices. Starts and ends at same vertex.
Theorem (Euler 1736)
Connected graph G has Euler circuit ⟺ every vertex has even degree.
Königsberg Bridge Problem
4 land masses connected by 7 bridges. All 4 vertices had odd degree → no Euler circuit exists. First graph theory proof.
Hierholzer's Algorithm
O(E): Find any circuit, then splice in sub-circuits at vertices with unused edges until all edges used.
// Euler Circuit Finder · Hierholzer animated
Check Animate Reset
Select graph type and click Check
Odd-degree vertices: — | Result: —
→∀
Euler Path — Start ≠ End Euler 2
Theorem
Connected G has Euler path (not circuit) ⟺ exactly 2 vertices have odd degree. Those two are the endpoints.
Applications
Route planning: garbage truck, mail delivery — traverse each street once.
Circuit board etching: draw each wire exactly once.
DNA assembly: de Bruijn graph Euler paths reconstruct sequences.
Odd vertices = 0 → Euler circuit | Odd = 2 → Euler path | Odd > 2 → neither
// Interactive Euler Path · draw edges yourself
New Euler Graph Show Solution Reset Trace
Click nodes in sequence to trace Euler path
Edges remaining: — | Completed: —
10.5b

Hamiltonian Paths & Circuits

∃
Hamiltonian — All Vertices Once NP-Hard
Hamiltonian Circuit
Circuit visiting every vertex exactly once. May skip edges. Named after W.R. Hamilton (1859 dodecahedron puzzle).
Dirac's Theorem (Sufficient)
If G simple, |V|≥3, and deg(v)≥|V|/2 for all v → Hamiltonian circuit exists.
Ore's Theorem (Sufficient)
If for every non-adjacent u,v: deg(u)+deg(v)≥|V| → Ham. circuit exists.
No Easy Characterization
Unlike Euler (polynomial check), Hamilton is NP-complete. No known efficient algorithm.
Euler: traverse ALL edges | Hamilton: visit ALL vertices
// Hamiltonian · try to find the circuit yourself
Show Solution Reset Check Dirac/Ore
Click nodes in order to build Hamiltonian circuit
Dirac: — | Ore: —
10.6

Shortest-Path Problems

D
Dijkstra's Algorithm — Single Source Greedy O((V+E)logV)
Problem
Given weighted graph G with non-negative weights and source s, find shortest path from s to all vertices.
Algorithm (Dijkstra 1959)
1. dist[s]=0, dist[v]=∞ for all others
2. Priority queue with all vertices
3. Extract min-dist vertex u
4. Relax neighbors: if dist[u]+w(u,v) < dist[v], update
5. Repeat until queue empty
Relaxation: dist[v] = min(dist[v], dist[u] + w(u,v))
Greedy Insight
Once a vertex is extracted from PQ, its distance is final. Negative weights break this (use Bellman-Ford).
// Dijkstra · click source · step through relaxations
Step ▶ Run All Reset New Graph
Click a node to set source
Source
In Queue
Finalized
Path Edge
Distances: —
FW
Floyd-Warshall — All Pairs DP O(V³)
Problem
Find shortest paths between ALL pairs of vertices. Handles negative weights (not negative cycles).
Recurrence
D[i][j] = min distance using first k vertices as intermediates:
D^k[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j])
Idea
Try every vertex k as potential intermediate. If going through k shortens i→j, use it. Dynamic programming.
Complexity
O(V³) time, O(V²) space. Good when V small, E dense.
// Floyd-Warshall · watch distance matrix evolve
Step k++ Run All Reset
Shows all-pairs distance matrix, k=0
10.7

Planar Graphs

χ
Euler's Formula · V − E + F = 2 Fundamental
Planar Graph
Can be drawn in the plane with no edge crossings. The drawing = planar embedding.
Euler's Formula (1758)
For any connected planar graph:
V − E + F = 2

F = number of faces (regions), including the unbounded outer face.

Corollaries (for simple planar, V≥3)
E ≤ 3V − 6    (general)     E ≤ 2V − 4    (bipartite/no triangle)
Verification
Cube: V=8,E=12,F=6 → 8-12+6=2 ✓ | Triangle: V=3,E=3,F=2 → 2 ✓
// Planar Embedder · drag nodes · crossings detected
Euler Formula Reset Layout
Drag nodes to eliminate crossings
V=— E=— F=— | V-E+F=— | Crossings=— | —
K
Kuratowski's Theorem Planarity Test
Kuratowski 1930
G is planar ⟺ G contains no subgraph that is a subdivision of K₅ or K₃,₃.
Subdivision
Replace edge (u,v) with path u→w₁→w₂→…→v. Adds vertices of degree 2. Called "topological minor".
Proofs of Non-Planarity
K₅: V=5,E=10 → 10 > 3(5)−6=9 → NOT planar
K₃,₃: V=6,E=9,bipartite → 9 > 2(6)−4=8 → NOT planar
Equivalent: Wagner's Theorem
G planar ⟺ no K₅ or K₃,₃ as graph minor (allowing edge contractions).
// K₅ and K₃,₃ subdivision explorer
Show K₅ Show K₃,₃ Subdivide Edge Reset
K₅ and K₃,₃ — the two forbidden minors
E ≤ 3V−6 check: —
10.8

Graph Coloring

χ
Chromatic Number χ(G) Coloring 1
Proper Coloring
Assign colors to vertices so no two adjacent vertices share a color.
Chromatic Number χ(G)
Minimum number of colors needed for proper coloring.
Known Values
χ(Kₙ) = n    χ(Bipartite) = 2    χ(Odd Cycle) = 3
χ(Even Cycle) = 2    χ(Tree) = 2    χ(Planar) ≤ 4
Brook's Theorem
χ(G) ≤ Δ(G) unless G is Kₙ or odd cycle (then χ=Δ+1).
Four Color Theorem (1976)
Every planar graph: χ(G) ≤ 4. First computer-assisted proof.
// Chromatic Number Explorer · greedy coloring
Step Auto Color Reset
Select a graph, then step through greedy coloring
Colors used: 0 | χ(G) = ? | Valid: —
🎨
Manual Coloring Challenge Interactive
Challenge
Try to color the graph using the minimum number of colors. No adjacent vertices can share a color!
Greedy Algorithm
Process vertices in some order. Assign smallest color not used by neighbors. Produces ≤ Δ+1 colors. Order matters!
Applications
Exam scheduling: exams=vertices, shared student=edge, color=time slot
Register allocation: live variables=vertices, interference=edge
Map coloring: 4 colors always enough for planar maps
Frequency assignment: radio stations needing different frequencies
// Color It Yourself · pick color · click vertex · avoid conflicts
Reset New Graph Auto Solve
Pick a color (circle), then click vertices
Colors used: 0 | Conflicts: 0 | Min needed: ?
—
Edge Coloring & χ'(G) Coloring 2
Edge Coloring
Color edges so no two adjacent edges (sharing a vertex) have same color. χ'(G) = edge chromatic number.
Vizing's Theorem (1964)
For simple graph: χ'(G) = Δ (Class 1) or χ'(G) = Δ+1 (Class 2).
Always: Δ ≤ χ'(G) ≤ Δ+1.
Examples
Kₙ (n even): χ' = n−1 = Δ (Class 1)
Kₙ (n odd): χ' = n = Δ+1 (Class 2)
Bipartite: χ' = Δ (König's theorem, always Class 1)
Application
Scheduling: tasks share a machine/time slot. Edge=task, vertex=machine, color=time slot.
// Edge Coloring · color edges so no two sharing vertex match
Auto Edge-Color Reset
Select graph and click Auto Edge-Color
Δ = — | χ'(G) = — | Class: —
GRAPH THEORY · COMPLETE INTERACTIVE REFERENCE
Kenneth H. Rosen — Discrete Mathematics and Its Applications, 8th Ed., Chapter 10
11 Interactive Modules · 25+ Simulations · Every Theorem with Live Example