Graph Theory and Network Mathematics

Graph theory, as Britannica summarizes it, is "a branch of mathematics concerned with networks of points connected by lines," and it traces its origin to a specific historical puzzle: in 1736, Leonhard Euler analyzed the city of Königsberg, which was split by a river into four landmasses connected by seven bridges, and asked whether a walker could cross every bridge exactly once and return to the start. Euler proved it was impossible by abstracting the landmasses into points and the bridges into lines connecting them — the first graph — and showing that such a walk exists only when every point has an even number of connecting lines, which Königsberg's did not, since three of its four landmasses were each connected by an odd number of bridges. Formally, a graph G = (V, E) consists of a set of vertices (or nodes) V and a set of edges E, each edge connecting two vertices; when edges have a direction (an edge from A to B is distinct from one from B to A) the graph is called directed, and otherwise undirected, with the choice of representation depending entirely on whether the relationship being modeled is inherently one-way or symmetric.

A worked example fixes the vocabulary. Take five vertices {A, B, C, D, E} with edges {A–B, A–C, B–C, B–D, D–E}. The degree of a vertex is its number of incident edges: A has degree 2, B has degree 3, C has degree 2, D has degree 2, and E has degree 1, and the sum of all degrees (2+3+2+2+1=10) is always exactly twice the number of edges, since each edge contributes to the degree count of two vertices. A path is a sequence of distinct vertices connected by edges, such as A–B–D–E, which has length 3 (three edges traversed); a cycle is a path that returns to its starting vertex without repeating any other vertex along the way, such as A–B–C–A. Because every vertex in this graph can be reached from every other vertex by following some sequence of edges, the graph is connected — it consists of a single connected component rather than several isolated clusters, a property that would fail immediately if, say, vertex E's only edge to D were removed and no other edge replaced it.

Computationally, a graph is usually stored as an adjacency matrix (an n×n table where entry (i,j) marks whether an edge connects vertex i and vertex j) or an adjacency list (for each vertex, the list of its neighbors), a distinction MIT's Mathematics for Computer Science course develops precisely because the choice affects the efficiency of every algorithm run on the graph afterward. An adjacency matrix makes checking whether any two specific vertices are connected fast (a single table lookup) but wastes space on graphs where most pairs of vertices are not directly connected, while an adjacency list stores only the edges that actually exist and is therefore far more space-efficient for such sparse graphs, at the cost of a slower check for any one specific pair. This representation choice matters directly for AI systems: a knowledge graph linking millions of entities, or the computation graph underlying a neural network's forward pass, is stored and traversed using exactly these structures, and the size and density of the graph — millions of sparsely connected entities versus a small, densely connected cluster — determines whether adjacency lists or matrices are the practical choice.

A tree is a connected graph with no cycles — equivalently, a connected graph on n vertices with exactly n − 1 edges, the minimum number of edges needed to keep every vertex reachable from every other. Remove any single edge from a tree and it falls apart into two disconnected pieces; add any single edge to a tree and it creates exactly one cycle — both properties follow directly from the n − 1 edge count. Trees are everywhere in AI: a decision tree partitions the feature space through a sequence of branching tests, a search tree in a planning or game-playing agent represents the space of possible action sequences from a starting state, and a taxonomy or ontology organizing concepts hierarchically is, structurally, a tree. Any connected graph contains at least one spanning tree — a subset of its edges that keeps all vertices connected while forming no cycles — and finding a minimum-weight spanning tree (the cheapest way to keep a weighted network connected without redundant links) is a classic graph algorithm with direct applications in network design, from telecommunications infrastructure to clustering algorithms.

Two traversal algorithms let you systematically visit every vertex reachable from a starting point: breadth-first search (BFS), which explores all vertices at distance 1 before any at distance 2, and depth-first search (DFS), which follows one branch as far as possible before backtracking to try another. Using the five-vertex graph from Lesson 1 — edges {A–B, A–C, B–C, B–D, D–E} — a BFS starting at A visits A first (distance 0), then its direct neighbors B and C (distance 1), then B's unvisited neighbor D (distance 2), and finally D's neighbor E (distance 3), producing the visiting order A, B, C, D, E, with C and D each visited only once even though multiple paths could reach them. This traversal order is exactly what an unweighted shortest-path search returns, since BFS discovers each vertex via the shortest possible route (fewest edges) from the start, which is why BFS, rather than DFS, is the algorithm of choice whenever "shortest route" in an unweighted network is the actual goal.

When edges carry weights — representing distance, cost, or travel time rather than a simple yes/no connection — the relevant question becomes finding the shortest weighted path, solved by algorithms such as Dijkstra's algorithm, a staple of the graph algorithms unit in MIT's discrete mathematics course. Unlike plain BFS, a shortest-weighted-path algorithm cannot simply count edges; it must repeatedly select the not-yet-finalized vertex with the smallest known total distance from the start and use it to try to shorten the distance estimates of its neighbors, gradually locking in the true shortest distance to every vertex in the graph. These weighted-network techniques underpin route planning in mapping applications, and the same underlying formalism — nodes, edges, and message-passing along them — is what graph neural networks (GNNs) generalize into a learnable model, propagating information between connected nodes across several rounds to make predictions about molecules, social networks, or recommendation systems represented as graphs.