Graph Theory Fundamentals

Definition: The mathematical study of graphs, structures composed of vertices (nodes) connected by edges, used to model pairwise relationships between objects.

How It Works

A graph G = (V, E) consists of a vertex set V and an edge set E, where each edge connects two vertices
Graphs are commonly represented in code as an adjacency matrix (a V × V grid of 0s and 1s) or an adjacency list (each vertex stores a list of its neighbors), the choice trades memory for lookup speed depending on how dense the graph is
Degree deg(v) counts how many edges touch vertex v, in a directed graph this splits into in-degree and out-degree
Handshaking Lemma: the sum of all vertex degrees equals twice the number of edges, ∑ deg(v) = 2|E|, since every edge contributes exactly 1 to two different vertices’ degree counts
A path visits a sequence of distinct vertices connected by edges, a cycle is a path that returns to its starting vertex
Eulerian Path: a path that visits every edge exactly once, exists if and only if a connected graph has exactly 0 or 2 vertices of odd degree, and forms an Eulerian circuit specifically when the count is 0, since it can then start and end at the same vertex
Hamiltonian Path: a path that visits every vertex exactly once, no simple general test for existence is known, and determining one is NP-complete
A Hamiltonian cycle is a Hamiltonian path that also returns to its starting vertex, the exact structure the classic Traveling Salesman Problem searches for the minimum-weight version of
A Planar Graph can be drawn on a 2D plane with no edges crossing, Euler’s Formula relates its structure: V - E + F = 2, where F counts faces, including the unbounded outer face
Graphs can be directed or undirected, weighted or unweighted, connected or disconnected, these properties determine which algorithms and theorems apply
A tree is a special connected graph with no cycles, exactly V - 1 edges for V vertices, and exactly one unique path between any two vertices
Graph coloring assigns labels (colors) to vertices so no two adjacent vertices share a color, the chromatic number is the minimum colors needed, and the Four Color Theorem proves any planar map needs at most 4
Breadth-first search (BFS) and depth-first search (DFS) are the two foundational traversal algorithms nearly every other graph algorithm builds on, exploring level by level versus branch by branch respectively

Key Graph Properties

Property	Definition	Example
Degree	Number of edges touching a vertex	A leaf node in a tree has degree 1
Connected	A path exists between every pair of vertices	A single social network component
Cycle	A path that returns to its starting vertex	A round-trip route
Bipartite	Vertices split into two sets, edges only cross between sets	Matching job applicants to job openings
Complete graph	Every pair of vertices is connected by an edge	A round-robin tournament schedule
DAG	Directed, acyclic, edges only flow one way	A build system’s task dependency order
Weighted	Edges carry a numeric cost or distance	Road networks with mileage
Tree	Connected, acyclic, `V - 1` edges	A file system directory structure

Under the Hood

This graph has 5 vertices and 5 edges. Vertex C has degree 3 (edges to A, B, D), vertices A, B, and D have degree 2 each, and vertex E has degree 1. Summing degrees: 2 + 2 + 3 + 2 + 1 = 10, matching 2|E| = 2 × 5 = 10, confirming the Handshaking Lemma holds exactly.

A path from A to E exists (A-C-D-E), so the graph is connected. A cycle exists too: A-B-C-A returns to its start using three distinct edges (A-B, B-C, C-A). Exactly two vertices have odd degree here, C (degree 3) and E (degree 1), so by the Eulerian path condition this graph has an Eulerian path that must start at one of them and end at the other: E-D-C-A-B-C uses all 5 edges (D-E, C-D, A-C, A-B, B-C) exactly once, starting at E and ending at C.

Note this graph is not itself a tree, it has 5 vertices but only needs 4 edges to stay connected and acyclic; the extra edge A-C is what creates the A-B-C-A cycle. Removing any one edge from that triangle would make the graph a tree instead.

Worked Example 1

Given: Verify the Handshaking Lemma on a graph with vertices of degree 2, 2, 3, 3, 4 (5 vertices total).
Step: Sum the degrees: 2 + 2 + 3 + 3 + 4 = 14. The lemma states this must equal 2|E|.
Answer: |E| = 14 / 2 = 7 edges, and since the sum is even, this degree sequence is at least parity-consistent with being a real graph.

Worked Example 2

Given: The Seven Bridges of Königsberg: four landmasses connected by seven bridges, with each landmass having degree 3, 3, 3, 5 respectively (counting bridge connections).
Step: An Eulerian path requires exactly 0 or 2 vertices of odd degree. All four landmasses here have odd degree (3, 3, 3, 5).
Answer: Since 4 vertices have odd degree, not 0 or 2, no Eulerian path exists, proving it’s impossible to walk across all seven bridges exactly once, the result Euler proved in 1736, founding graph theory.

Worked Example 3

Given: A connected planar graph has 6 vertices and 10 edges. Find the number of faces using Euler’s Formula.
Step: Euler’s Formula states V - E + F = 2, so F = 2 - V + E = 2 - 6 + 10.
Answer: F = 6 faces, including the unbounded outer face, meaning 5 bounded regions are enclosed by the graph’s edges.

Worked Example 4

Given: Determine whether a graph with 7 vertices and 6 edges, all vertices connected in a single component with no cycles, is a tree.
Step: A tree requires exactly V - 1 edges for a connected, acyclic graph. Here V - 1 = 7 - 1 = 6, which matches the given edge count exactly.
Answer: Yes, this graph is a tree, connected, acyclic, and with precisely the edge count the tree property requires.

Why It Matters

Provides the mathematical foundation underlying network topology, internet routing protocols, social graph analysis, and circuit layout design
Gives a precise, shared vocabulary (degree, path, cycle, connectivity) that transfers directly across fields, the same terms describe a social network and a circuit board
Directly informs algorithm choice, shortest-path problems (Dijkstra’s algorithm), network flow (Ford-Fulkerson), and dependency resolution (topological sort) are all graph algorithms with real-world software applications
Determines computational feasibility, recognizing a problem is equivalent to finding a Hamiltonian path (NP-complete) versus an Eulerian path (solvable in polynomial time) changes the entire approach to solving it
Models real infrastructure directly, power grids, transportation networks, and the internet’s physical topology are all analyzed as graphs to find bottlenecks and plan capacity
Underlies compiler and build-system design, dependency graphs must be acyclic (a DAG) for a topological sort to produce a valid build or execution order
Enables scheduling and resource allocation, graph coloring directly solves problems like assigning exam times so no student has two exams at once
Makes bottleneck and vulnerability analysis rigorous, identifying which single vertex or edge, if removed, would disconnect a network points directly at its weakest infrastructure point
Gives social network analysis a formal toolkit, centrality measures, clustering, and community detection are all graph-theoretic computations over a friendship or follower graph

Common Pitfalls

Confusing Eulerian paths (efficiently solvable in O(E) time via known conditions) with Hamiltonian paths (NP-complete, no known efficient general algorithm)
Forgetting that the Handshaking Lemma implies the number of odd-degree vertices in any graph is always even, a quick sanity check for whether a claimed degree sequence is even possible
Assuming a graph is planar just because it can be drawn without obvious crossings, planarity requires proving no valid crossing-free drawing exists at all, not just failing to find one
Choosing an adjacency matrix for a large, sparse graph, wasting O(V^2) memory on mostly-zero entries when an adjacency list would represent the same graph in far less space
Treating directed and undirected graph properties as interchangeable, degree splits into in-degree and out-degree for directed graphs, and the Handshaking Lemma’s exact form changes accordingly
Confusing a tree with any acyclic graph, a tree must also be connected, a disconnected acyclic graph is a forest, a collection of separate trees
Assuming an Eulerian path condition applies without first checking the graph is connected, the odd-degree count rule only guarantees a path within a single connected component
Confusing a graph’s chromatic number with its maximum degree, the two are related by an upper bound but are not generally equal
Forgetting that Euler’s Formula (V - E + F = 2) only applies to connected planar graphs, applying it to a disconnected graph without adjustment gives a wrong face count
Overlooking self-loops and multi-edges when counting degree, a self-loop typically adds 2 to a vertex’s degree, not 1, since both ends of the edge attach to the same vertex
Assuming a graph representation choice is free of tradeoffs, an adjacency list makes edge iteration fast but edge-existence checks slower than an adjacency matrix, and vice versa

Comparison

	Eulerian Path	Hamiltonian Path	Shortest Path	Minimum Spanning Tree
Visits	Every edge exactly once	Every vertex exactly once	Vertices along one specific route	All vertices, minimum total edge weight
Existence test	Simple, 0 or 2 odd-degree vertices	No known efficient general test	Always exists if connected	Always exists if connected
Complexity to find	Polynomial, `O(E)`	NP-complete	Polynomial (Dijkstra, Bellman-Ford)	Polynomial (Kruskal, Prim)
Real-world use	Route inspection, mail delivery	Traveling salesman variants	GPS navigation, network routing	Network design, clustering
Guaranteed to exist	Only if degree condition holds	Not guaranteed, checked case by case	Yes, if source and destination are connected	Yes, for any connected weighted graph
Typical algorithm	Fleury’s or Hierholzer’s algorithm	Backtracking, held-karp DP for small n	Dijkstra, Bellman-Ford, A*	Kruskal’s or Prim’s algorithm

Example

The Seven Bridges of Königsberg problem, solved by Leonhard Euler in 1736, proved no walking route could cross all seven bridges exactly once, the founding result of graph theory as a distinct mathematical field, derived purely from the degree-parity argument shown above.

Google’s PageRank algorithm treats the entire web as a massive directed graph, web pages as vertices, hyperlinks as directed edges, and computes a page’s importance from the graph’s link structure, one of the most consequential real-world applications of graph theory in software.

Referenced by

Dig deeper

Spot an error in this note?