Study guide
8.4 Graph Theory, Networks, Trees & Algorithms
NBPTS Adolescence & Young Adulthood / Mathematics Exam
Track your progress as you read
Finished sections get a check mark.
1 Chapter 1: Number Systems & Number Theory
1.1 Real and Complex Number Systems & Field Axioms 1.2 Number Theory, Divisibility, Primes & Modular Arithmetic 1.3 Sequences, Series & Summation Notation
2 Chapter 2: Polynomials & Algebraic Structures
2.1 Polynomial Operations, Factoring & Factor/Remainder Theorems 2.2 The Fundamental Theorem of Algebra & Polynomial Roots 2.3 Rational Expressions, Radical Equations & Inequalities 2.4 Matrices, Systems of Equations & Linear Algebra
3 Chapter 3: Functions & Functional Analysis
3.1 Foundations of Functions: Domain, Range & Notation 3.2 Function Transformations, Operations, Composition & Inverses 3.3 Exponential and Logarithmic Functions & Applications 3.4 Rational Functions, Asymptotes & Discontinuities
4 Chapter 4: Trigonometry & Periodic Phenomena
4.1 Angle Measure, Radians & The Unit Circle 4.2 Trigonometric Graphs, Amplitude, Period & Phase Shifts 4.3 Trigonometric Identities & Solving Trigonometric Equations 4.4 Laws of Sines and Cosines, Vectors & Polar Coordinates
5 Chapter 5: Geometry & Measurement
5.1 Axiomatic Geometry, Congruence, Similarity & Proof 5.2 Circle Theorems: Tangents, Chords, Secants & Angles 5.3 2D & 3D Measurement: Area, Surface Area & Volume 5.4 Coordinate Geometry & Geometric Transformations
6 Chapter 6: Single-Variable Calculus
6.1 Limits, Continuity & Average vs. Instantaneous Rate of Change 6.2 Differentiation Rules, Chain Rule & Implicit Differentiation 6.3 Applications of Derivatives: Curve Sketching, Extrema & Optimization 6.4 Definite & Indefinite Integrals, Riemann Sums & FTC 6.5 Volumes of Solids of Revolution: Disk, Washer & Shell Methods
7 Chapter 7: Statistics & Data Analysis
7.1 Descriptive Statistics, Data Distributions & Visual Displays 7.2 Bivariate Data, Scatterplots, Correlation & Linear Regression 7.3 Study Design, Sampling Methods & Sources of Bias 7.4 Inferential Statistics: Confidence Intervals & Hypothesis Testing
8 Chapter 8: Probability & Discrete Mathematics
8.1 Principles of Probability, Conditional Probability & Independence 8.2 Probability Distributions: Binomial & Normal Models 8.3 Combinatorics: Permutations, Combinations & Binomial Theorem 8.4 Graph Theory, Networks, Trees & Algorithms
9 Chapter 9: Mathematical Reasoning, Proof & Modeling
9.1 Propositional Logic, Truth Tables & Quantifiers 9.2 Proof Techniques & Mathematical Induction 9.3 The Mathematical Modeling Cycle & Secondary Applications 9.4 Historical Development of Mathematical Ideas & Cultural Contributions 9.5 Precise Communication of Mathematical Ideas, Definitions & Justification
10 Chapter 10: Secondary Mathematics Pedagogy & NBPTS Standards
10.1 The NBPTS Five Core Propositions & EAYA Mathematics Standards 10.2 Standards for Mathematical Practice & Productive Classroom Discourse 10.3 Formative Assessment, Student Error Analysis & Misconceptions 10.4 Component 1 Assessment Structure & Constructed-Response Strategy
8.4 Graph Theory, Networks, Trees & Algorithms
Key Takeaways Explain This Topic AI
A graph G = (V, E) consists of vertices and edges; the Handshaking Lemma dictates that the sum of all vertex degrees equals twice the total number of edges (∑ deg(v) = 2|E|), proving that every graph must possess an even number of odd-degree vertices.
An Euler circuit traverses every edge of a graph exactly once and returns to the origin, which exists in a connected graph if and only if every vertex has an even degree; an Euler path exists if and only if exactly two vertices have odd degree.
A Hamiltonian cycle visits every vertex of a graph exactly once before returning to the start; unlike Eulerian traversability, Hamiltonian cycle determination is an NP-complete problem with no simple degree-parity criterion.
Planar graphs can be embedded in the Euclidean plane without intersecting edges, satisfying Euler's Formula V - E + F = 2 for connected planar graphs, from which the edge bound E ≤ 3V - 6 proves the non-planarity of K_5 and K_{3,3} via Kuratowski's Theorem.
A tree is a connected acyclic graph on n vertices possessing exactly n - 1 edges; greedy network optimization algorithms include Kruskal's and Prim's algorithms for Minimum Spanning Trees (MST) and Dijkstra's algorithm for shortest paths with non-negative edge weights.
Last updated: September 2026
8.4 Graph Theory, Networks, Trees & Algorithms
Graph theory is the mathematical study of structural connections between discrete objects. Originating in Leonhard Euler's 1736 resolution of the Königsberg bridge problem, modern graph theory underpins telecommunication networks, transport logistics, circuit design, and computer science algorithms. In secondary mathematics instruction (grades 9–12), graph theory provides an intuitive yet analytically rigorous playground for developing topological proofs, recursive structures, algorithmic thinking, and discrete optimization models.
1. Graph Fundamentals, Degree Sequences & The Handshaking Lemma
A graph G = ( V , E ) G = (V, E) G = ( V , E ) is an ordered pair comprising a set of vertices (or nodes) V V V and a set of edges (or links) E E E , where each edge e ∈ E e \in E e ∈ E connects an unordered pair of vertices { u , v } \{u, v\} { u , v } . In a simple graph , loops (edges connecting a vertex to itself) and multiple edges between the same pair of vertices are forbidden.
Vertex Degree and Degree Sequences
The degree of a vertex v v v , denoted deg ( v ) \operatorname{deg}(v) deg ( v ) , is the number of edges incident to v v v (with self-loops contributing 2). The ordered list of vertex degrees, typically in non-increasing order, forms the degree sequence of the graph.
The Handshaking Lemma (Euler's Degree-Sum Theorem)
The foundational theorem of graph theory links vertex degrees directly to edge cardinality:
Important
Theorem (The Handshaking Lemma): In any graph G = ( V , E ) G = (V, E) G = ( V , E ) : ∑ v ∈ V deg ( v ) = 2 ∣ E ∣ \sum_{v \in V} \operatorname{deg}(v) = 2|E| ∑ v ∈ V deg ( v ) = 2∣ E ∣
Proof: Each edge e = { u , v } e = \{u, v\} e = { u , v } possesses exactly two endpoints. When calculating the sum of degrees across all vertices, edge e e e is counted exactly twice: once in deg ( u ) \operatorname{deg}(u) deg ( u ) and once in deg ( v ) \operatorname{deg}(v) deg ( v ) . Thus, the sum of all degrees equals twice the number of edges.
Fundamental Parity Corollary
An immediate and powerful corollary governs odd-degree vertices:
Corollary: Every graph must contain an even number of vertices of odd degree .
Proof: Partition V V V into V even V_{\text{even}} V even and V odd V_{\text{odd}} V odd . Then: ∑ v ∈ V deg ( v ) = ∑ v ∈ V even deg ( v ) + ∑ v ∈ V odd deg ( v ) = 2 ∣ E ∣ \sum_{v \in V} \operatorname{deg}(v) = \sum_{v \in V_{\text{even}}} \operatorname{deg}(v) + \sum_{v \in V_{\text{odd}}} \operatorname{deg}(v) = 2|E| ∑ v ∈ V deg ( v ) = ∑ v ∈ V even deg ( v ) + ∑ v ∈ V odd deg ( v ) = 2∣ E ∣ The total sum 2 ∣ E ∣ 2|E| 2∣ E ∣ is even, and the sum over V even V_{\text{even}} V even is even. Therefore, the sum ∑ v ∈ V odd deg ( v ) \sum_{v \in V_{\text{odd}}} \operatorname{deg}(v) ∑ v ∈ V odd deg ( v ) must be even. A sum of odd integers can be even if and only if there is an even number of terms. Hence, ∣ V odd ∣ |V_{\text{odd}}| ∣ V odd ∣ is even.
2. Walks, Paths, Circuits & Eulerian vs. Hamiltonian Traversability
Navigating network topology requires precise distinctions among route classifications:
Walk: An alternating sequence of vertices and edges v 0 , e 1 , v 1 , e 2 , … , e k , v k v_0, e_1, v_1, e_2, \dots, e_k, v_k v 0 , e 1 , v 1 , e 2 , … , e k , v k .
Trail: A walk with no repeated edges .
Path: A walk with no repeated vertices (and consequently no repeated edges).
Circuit: A closed trail (starts and ends at the same vertex, v 0 = v k v_0 = v_k v 0 = v k , with no repeated edges).
Cycle: A closed path (starts and ends at the same vertex, with no other repeated vertices).
Eulerian Graphs (Edge-Focused Traversability)
An Euler trail (or path) visits every edge of a graph exactly once. An Euler circuit is an Euler trail that starts and terminates at the same vertex.
Important
Euler's Theorem (Eulerian Graphs): Let G G G be a connected graph (or connected up to isolated vertices):
G G G contains an Euler circuit if and only if every vertex has an even degree .
G G G contains an Euler trail (open path) if and only if exactly two vertices have odd degree . The trail must begin at one odd vertex and end at the other.
The Seven Bridges of Königsberg (1736): Four landmasses were connected by seven bridges over the Pregel River. The corresponding multigraph had 4 vertices with degrees 3 , 3 , 3 , 5 3, 3, 3, 5 3 , 3 , 3 , 5 . Because all 4 vertices had odd degrees (exceeding the allowable 0 or 2), Euler proved that traversing all seven bridges without retracing any bridge was physically impossible. +-----------------------------------------------------------------------------+
- | EULERIAN VS. HAMILTONIAN TRAVERSABILITY |
- | |
- | Feature Eulerian Routing Hamiltonian Routing |
- | ----------------------------------------------------------------------- |
- | Traversal Goal Every EDGE exactly once Every VERTEX exactly once
- | Algorithmic Check Degree parity check: No necessary/sufficient |
- | All even (circuit) or degree parity criteria; |
- | exactly two odd (trail) NP-complete problem |
- | Computational Time Polynomial O(|E|) (Fleury) Exponential in general |
- | Real-World Context Street sweeper, mail carrier, Traveling Salesperson, |
- | snowplow route, pipe inspector delivery truck route |
- +-----------------------------------------------------------------------------+
- Hamiltonian Graphs (Vertex-Focused Traversability)
A Hamiltonian path visits every vertex in G G G exactly once. A Hamiltonian cycle is a closed cycle visiting every vertex once and returning to the starting vertex.
Computational Contrast: While Eulerian traversability is solvable in polynomial time O ( ∣ E ∣ ) O(|E|) O ( ∣ E ∣ ) by inspecting degree parities, determining whether an arbitrary graph contains a Hamiltonian cycle is NP-complete . No simple local degree condition characterizes Hamiltonian graphs. However, classic sufficient theorems exist:
Dirac's Theorem (1952): If G G G is a simple graph with n ≥ 3 n \ge 3 n ≥ 3 vertices, and deg ( v ) ≥ n / 2 \operatorname{deg}(v) \ge n/2 deg ( v ) ≥ n /2 for every vertex v v v , then G G G is Hamiltonian.
Ore's Theorem (1960): If G G G is a simple graph with n ≥ 3 n \ge 3 n ≥ 3 vertices, and deg ( u ) + deg ( v ) ≥ n \operatorname{deg}(u) + \operatorname{deg}(v) \ge n deg ( u ) + deg ( v ) ≥ n for every pair of non-adjacent vertices u , v u, v u , v , then G G G is Hamiltonian.
3. Planar Graphs & Euler's Polyhedral Formula
A graph G G G is planar if it can be drawn (embedded) in the Euclidean plane R 2 \mathbb{R}^2 R 2 such that no two edges intersect except at their common incident vertices. A planar drawing divides the plane into contiguous regions called faces ( F F F ), including the unbounded exterior face.
Euler's Formula for Planar Graphs
Important
Theorem (Euler's Planar Formula): For any connected planar graph with V V V vertices, E E E edges, and F F F faces: V − E + F = 2 V - E + F = 2 V − E + F = 2
Planarity Edge Bounds
In any simple planar graph with V ≥ 3 V \ge 3 V ≥ 3 , every face boundary must consist of at least 3 edges. Since each edge borders at most 2 faces, 2 E ≥ 3 F ⟹ F ≤ 2 3 E 2E \ge 3F \implies F \le \frac{2}{3}E 2 E ≥ 3 F ⟹ F ≤ 3 2 E . Substituting into Euler's formula: V − E + 2 3 E ≥ 2 ⟹ V − 1 3 E ≥ 2 ⟹ E ≤ 3 V − 6 V - E + \frac{2}{3}E \ge 2 \implies V - \frac{1}{3}E \ge 2 \implies E \le 3V - 6 V − E + 3 2 E ≥ 2 ⟹ V − 3 1 E ≥ 2 ⟹ E ≤ 3 V − 6
For bipartite planar graphs (which contain no odd cycles, so every face has at least 4 boundary edges, 2 E ≥ 4 F ⟹ F ≤ 1 2 E 2E \ge 4F \implies F \le \frac{1}{2}E 2 E ≥ 4 F ⟹ F ≤ 2 1 E ): E ≤ 2 V − 4 E \le 2V - 4 E ≤ 2 V − 4
Proving Non-Planarity of K 5 K_5 K 5 and K 3 , 3 K_{3,3} K 3 , 3
Complete Graph K 5 K_5 K 5 : V = 5 , E = ( 5 2 ) = 10 V = 5, E = \binom{5}{2} = 10 V = 5 , E = ( 2 5 ) = 10 . The planar bound requires E ≤ 3 ( 5 ) − 6 = 9 E \le 3(5) - 6 = 9 E ≤ 3 ( 5 ) − 6 = 9 . Because 10 > 9 10 > 9 10 > 9 , K 5 K_5 K 5 is non-planar.
Complete Bipartite Graph K 3 , 3 K_{3,3} K 3 , 3 (Utility Graph): V = 6 , E = 3 × 3 = 9 V = 6, E = 3 \times 3 = 9 V = 6 , E = 3 × 3 = 9 . Since K 3 , 3 K_{3,3} K 3 , 3 is bipartite (triangle-free), it requires E ≤ 2 ( 6 ) − 4 = 8 E \le 2(6) - 4 = 8 E ≤ 2 ( 6 ) − 4 = 8 . Because 9 > 8 9 > 8 9 > 8 , K 3 , 3 K_{3,3} K 3 , 3 is non-planar.
Kuratowski's Theorem (1930): A graph is planar if and only if it contains no subgraph that is a subdivision of (or homeomorphic to) K 5 K_5 K 5 or K 3 , 3 K_{3,3} K 3 , 3 .
4. Trees, Spanning Trees & Minimum Spanning Tree (MST) Algorithms
A tree is a connected, acyclic, undirected simple graph. A forest is a disjoint collection of trees.
Equivalent Characterizations of Trees
For a graph T T T with n n n vertices, the following statements are mathematically equivalent:
T T T is connected and contains no cycles.
T T T has no cycles and has exactly n − 1 n - 1 n − 1 edges.
T T T is connected and has exactly n − 1 n - 1 n − 1 edges.
There is a unique simple path between any pair of vertices in T T T .
T T T is minimally connected (removing any edge disconnects the graph).
T T T is maximally acyclic (adding any edge between non-adjacent vertices creates a unique cycle).
Spanning Trees and Minimum Spanning Trees (MST)
A spanning tree of a connected graph G = ( V , E ) G = (V, E) G = ( V , E ) is a subgraph T = ( V , E T ) T = (V, E_T) T = ( V , E T ) that is a tree and includes every vertex in V V V . If G G G has non-negative edge weights w ( e ) w(e) w ( e ) , a Minimum Spanning Tree (MST) minimizes the total weight ∑ e ∈ E T w ( e ) \sum_{e \in E_T} w(e) ∑ e ∈ E T w ( e ) .
Greedy MST Algorithms
Kruskal's Algorithm (Edge-Centric Greedy):
Sort all edges in E E E in non-decreasing order of weight: w ( e 1 ) ≤ w ( e 2 ) ≤ ⋯ ≤ w ( e m ) w(e_1) \le w(e_2) \le \dots \le w(e_m) w ( e 1 ) ≤ w ( e 2 ) ≤ ⋯ ≤ w ( e m ) .
Initialize T T T as an empty forest containing all vertices.
Iterate through the sorted edges: add edge e i e_i e i to T T T if and only if adding e i e_i e i does not create a cycle (managed via Disjoint-Set / Union-Find data structures).
Terminate when T T T contains exactly n − 1 n - 1 n − 1 edges.
Prim's Algorithm (Vertex-Centric Greedy):
Start with an arbitrary root vertex r ∈ V r \in V r ∈ V ; set V T = { r } V_T = \{r\} V T = { r } and E T = ∅ E_T = \emptyset E T = ∅ .
At each step, find the minimum-weight edge e = { u , v } e = \{u, v\} e = { u , v } such that u ∈ V T u \in V_T u ∈ V T and v ∈ V ∖ V T v \in V \setminus V_T v ∈ V ∖ V T .
Add v v v to V T V_T V T and e e e to E T E_T E T .
Repeat until V T = V V_T = V V T = V .
5. Shortest Path Optimization: Dijkstra's Algorithm
While MST algorithms connect all vertices with minimum total network cost, finding the shortest path between two specific vertices requires a different optimization.
Dijkstra's Single-Source Shortest Path Algorithm
Given a weighted graph G = ( V , E ) G = (V, E) G = ( V , E ) with non-negative edge weights ( w ( u , v ) ≥ 0 w(u, v) \ge 0 w ( u , v ) ≥ 0 ) and a designated source vertex s s s :
Initialization: Set dist ( s ) = 0 \operatorname{dist}(s) = 0 dist ( s ) = 0 and dist ( v ) = ∞ \operatorname{dist}(v) = \infty dist ( v ) = ∞ for all v ≠ s v \ne s v = s . Let unvisited set Q = V Q = V Q = V .
Selection: Extract vertex u ∈ Q u \in Q u ∈ Q with the minimum tentative distance dist ( u ) \operatorname{dist}(u) dist ( u ) .
Relaxation: For each unvisited neighbor v v v of u u u : alt = dist ( u ) + w ( u , v ) \text{alt} = \operatorname{dist}(u) + w(u, v) alt = dist ( u ) + w ( u , v ) If alt < dist ( v ) \text{alt} < \operatorname{dist}(v) alt < dist ( v ) , update dist ( v ) = alt \operatorname{dist}(v) = \text{alt} dist ( v ) = alt and set predecessor prev ( v ) = u \operatorname{prev}(v) = u prev ( v ) = u .
Iteration: Remove u u u from Q Q Q . Repeat steps 2–3 until Q = ∅ Q = \emptyset Q = ∅ .
Limitation: Dijkstra's algorithm fails in the presence of negative edge weights (which require the Bellman-Ford algorithm).
6. Secondary Pedagogical Traps & Instructional Interventions
Accomplished mathematics teachers anticipate common student hurdles in graph theory:
Misconception 1: Conflating Eulerian and Hamiltonian Routing
Students habitually confuse the edge-traversal requirement of Euler circuits with the vertex-traversal requirement of Hamiltonian cycles, attempting to apply vertex degree parity tests to Traveling Salesperson problems.
Pedagogical Intervention: Utilize concrete occupational metaphors. Euler problems represent "The Street Inspector / Snowplow Problem" : every road (edge) must be plowed or inspected, regardless of how many times the plow passes through an intersection (vertex). Hamiltonian problems represent "The Delivery Van / School Bus Problem" : the driver must stop at each house or store (vertex) exactly once, skipping unnecessary connecting streets. Emphasize that Euler routing is computationally simple ( O ( ∣ E ∣ ) O(|E|) O ( ∣ E ∣ ) degree inspection), whereas Hamiltonian routing is an NP-complete search problem.
Misconception 2: Forgetting the Exterior Face in Euler's Formula
When verifying V − E + F = 2 V - E + F = 2 V − E + F = 2 , students consistently count only the bounded interior polygons and omit the surrounding unbounded infinite region, obtaining V − E + F = 1 V - E + F = 1 V − E + F = 1 .
Pedagogical Intervention: Connect planar graphs to spherical polyhedra. Model a graph drawn on the surface of a globe. Puncturing the center of one face and stretching the spherical skin flat onto a table transforms the punctured face into the vast exterior boundary surrounding the planar drawing. This demonstrates why the exterior region is an authentic, topologically necessary face.
Misconception 3: Cyclic Edge Inclusion in Kruskal's Algorithm
Students executing Kruskal's algorithm mechanically select the next smallest available edge, forgetting to verify whether that edge links two vertices that already belong to the same connected component.
Pedagogical Intervention: Require students to maintain a connected component table or use colored highlighters during manual execution. When considering an edge, check if both endpoints share the same color. If both endpoints are already green, adding the edge creates a cycle ⟹ \implies ⟹ reject the edge.