Graph Theory: Nodes, Edges and Matrices
In 1736 Leonhard Euler proved that nobody could walk through the town of Königsberg and cross each of its seven bridges exactly once. To do it, he threw away the map. Only two things mattered: the land masses and the bridges between them. That step started graph theory.
A graph is the simplest structure that can hold relations. Roads between cities, links between web pages, friends in a social network, atoms in a molecule and neurons in a brain all fit the same mold. Learn the tools once and you can use them on all of these.
Part 1: the words you need to talk about graphs.
Part 2: the classic algorithms, from search to shortest paths to flows.
Part 3: the surprise. A graph is also a matrix, and the matrix knows where the clusters are.
The Basics
A graph G = (V, E) is a set of vertices (or nodes) V and a set of edges E. Each edge joins two vertices. We write n for the number of vertices and m for the number of edges.
- Degree: the number of edges that touch a vertex. Every edge has two ends, so the degrees of all vertices add up to 2m. This is the handshake lemma, and it explains why the number of odd degree vertices is always even.
- Directed or undirected: a follow on a social network goes one way (directed). A friendship goes both ways (undirected).
- Weighted or unweighted: edges can carry a number, such as a distance, a cost or a capacity.
- Path: a sequence of edges that leads from one vertex to another. A cycle is a path that returns to where it started.
- Connected component: a largest group of vertices where any vertex can reach any other.
A few kinds of graphs show up again and again:
- Trees are connected and have no cycles. A tree with n vertices always has n − 1 edges. File systems, family trees and parse trees are all trees.
- DAGs (directed acyclic graphs) have directions but no cycles. Task dependencies, git histories and spreadsheet formulas form DAGs.
- Bipartite graphs split their vertices into two groups so that every edge crosses between them: users and products, workers and jobs. A graph is bipartite exactly when it has no cycle of odd length.
- Complete graphs connect every pair of vertices and have n(n − 1)/2 edges.
- Planar graphs can be drawn on paper with no crossing edges. Every map of countries is one, which is why four colors always suffice to color a map.
Storing a Graph
Computers store graphs in two main ways. An adjacency list keeps, for each vertex, a list of its neighbors. It needs memory proportional to n + m. An adjacency matrix A is an n × n table where Aij = 1 if an edge joins i and j, and 0 if not. It needs n² cells, but it answers "are i and j linked?" in one lookup.
Most real graphs are sparse. A social network may have a billion users, but each user has a few hundred friends. So programs mostly use lists (or compressed sparse matrices). The dense matrix still matters, because it lets us bring linear algebra to graphs. Keep it in mind for part 3.
Hover a node or a matrix cell. Switch the power k to see what Ak counts.
- Selected entry
- Hover a cell
- Walks it counts
- None selected
- Adjacency list
- Triangles, trace(A³) / 6
Common Algorithms
Breadth-First and Depth-First Search
Most graph algorithms build on one of two ways to explore a graph. Breadth-first search (BFS) visits the start, then all its neighbors, then all their neighbors, and so on, ring by ring. It keeps the waiting vertices in a queue. In an unweighted graph, BFS finds the path with the fewest edges.
Depth-first search (DFS) instead follows one path as far as it goes and only then backs up. It keeps a stack (or uses recursion). DFS finds cycles, finds connected components, and solves mazes. Both run in O(n + m) time, which is as fast as reading the graph at all. See computational complexity for what this notation means.
Topological Sort
Given a DAG of tasks, in which order can you run them so that each task comes after everything it depends on? A topological sort answers this. One way: run DFS and list vertices in reverse order of when you finish them. Another way (Kahn's algorithm): keep removing a vertex with no incoming edges. Build tools like make, package managers and spreadsheet engines all do this. If the sort fails, the graph has a cycle, which means a circular dependency.
Shortest Paths
Once edges have weights, the path with the fewest edges may not be the cheapest. Dijkstra's algorithm grows a set of settled vertices whose shortest distance it knows for sure. Each round it settles the closest unsettled vertex, then checks whether going through it gives any neighbor a shorter route. With a binary heap it runs in O((n + m) log n). It only works when no weight is negative.
Try both below. Notice how BFS ignores the weights, while Dijkstra happily takes a longer detour of cheap edges.
Click a node to make it the start. Step through the search or let it play. Numbers under nodes show the best known distance, green edges show the tree of best paths.
- Visited in order
- none yet
- Queue
Orange: waiting in the queue. Filled orange: being processed. Green: done. For BFS the number counts edges, for Dijkstra it sums weights.
Two relatives fill the gaps. The Bellman-Ford algorithm handles negative weights. It relaxes every edge n − 1 times, which costs O(n·m). If a further round still improves some distance, the graph has a negative cycle. Currency traders use this trick: take the negative log of each exchange rate, and a negative cycle becomes a loop of trades that makes money.
A* search adds a guess of the remaining distance to each vertex, such as the straight line distance on a map. It then explores the most promising vertices first. As long as the guess never overestimates, A* still finds the shortest path, usually after looking at far fewer vertices. Route planners and game characters use it.
Minimum Spanning Trees
Suppose you want to connect a set of towns with power lines at the lowest total cost. You need a minimum spanning tree: a tree that touches every vertex and has the smallest total weight. Two greedy algorithms find it.
- Kruskal's algorithm sorts all edges by weight and adds each edge unless it would close a cycle. A union-find structure checks that in almost constant time. Total cost: O(m log m).
- Prim's algorithm grows one tree from a start vertex and always adds the cheapest edge leaving it. It looks a lot like Dijkstra.
Here is a first hint of clustering. Build the minimum spanning tree of your data points, then delete its k − 1 longest edges. The tree falls apart into k groups. This is single linkage clustering.
Maximum Flow and Minimum Cut
Treat each edge as a pipe with a capacity. How much water can flow from a source s to a sink t? The Ford-Fulkerson method keeps finding a path with spare capacity and pushes flow along it. The Edmonds-Karp version picks those paths with BFS and runs in O(n·m²).
The max-flow min-cut theorem says the maximum flow equals the capacity of the smallest set of pipes whose removal separates s from t. Flows match workers to jobs, plan logistics and cut images into foreground and background. Remember the word "cut". It comes back.
Where It Gets Hard
Back to Euler. A walk that uses every edge once exists exactly when the graph is connected and has zero or two vertices of odd degree. Königsberg had four, so no such walk existed. You can check this in linear time.
Change one word and the problem becomes much harder. A path that visits every vertex once is a Hamiltonian path, and deciding whether one exists is NP-complete. Its weighted cousin, the travelling salesman problem, asks for the cheapest round trip through all cities. No one knows a fast algorithm for either.
Graph coloring follows the same pattern. Can you give each vertex a color so that no edge joins two vertices of the same color? Two colors: easy, run BFS and check that the graph is bipartite. Three colors: NP-complete. Compilers still color graphs to assign variables to CPU registers, and schools do it to schedule exams without clashes. They rely on good heuristics.
Graphs Are Matrices
Now take the adjacency matrix seriously. Not as storage, but as a linear map. Many facts about the graph turn into facts about the matrix, and the tools of linear algebra (products, eigenvalues and eigenvectors) start to answer graph questions.
Matrix Powers Count Walks
Look at an entry of A²:
Each term is 1 only when i links to k and k links to j. So the sum counts walks of length 2 from i to j. The same argument works for any power: (Ak)ij counts the walks of length k. The diagonal of A³ counts walks that return home in three steps, which are triangles. Each triangle shows up six times (three start points, two directions), so the number of triangles is trace(A³) / 6. Go back to the matrix demo above and try it.
This view goes further. One BFS step is a matrix times a vector: multiply A by the indicator vector of the current frontier and you get the next one. Swap ordinary arithmetic for (min, +) and the same product computes shortest paths. The GraphBLAS standard builds a whole graph library on this idea, so graph code can run on fast sparse matrix routines.
Eigenvectors Rank Nodes
Which vertex is most important? A simple answer: you are important if important vertices link to you. Write each vertex's score as xi and demand that it is proportional to the sum of its neighbors' scores:
That is an eigenvector equation. This eigenvector centrality uses the eigenvector of the largest eigenvalue. For a connected graph, the Perron-Frobenius theorem promises that this eigenvector has only positive entries, so the scores make sense.
PageRank, the idea that started Google, adds a random surfer. The surfer follows a random link on each page, and with probability 1 − d (d is about 0.85) jumps to a random page instead. Let P be the matrix that moves the surfer one step. PageRank is the eigenvector with eigenvalue 1 of
It tells you what share of its time the surfer spends on each page in the long run. Google computed it with power iteration: start with any vector and keep multiplying by G until it stops changing.
The Laplacian Finds Clusters
Let D be the diagonal matrix of degrees. The graph Laplacian is
It looks plain, but it hides a useful identity. Put a number xi on each vertex. Then
This sum is small when linked vertices get similar numbers. Three facts follow.
- No eigenvalue is negative, since the sum of squares can't be. The smallest eigenvalue is always 0, with the constant vector (1, 1, …, 1) as its eigenvector.
- The number of zero eigenvalues equals the number of connected components. Give every vertex of one component the same value and every other vertex 0: each edge then adds 0 to the sum. Pure linear algebra counts the pieces of a graph.
- The second smallest eigenvalue λ2 measures how well connected the graph is. Miroslav Fiedler called it the algebraic connectivity. It is above 0 exactly when the graph is connected, and small when a few edges hold the graph together.
Now the payoff. Say we want to split the vertices into two groups and cut as few edges as possible. Label one group xi = +1 and the other −1. Each cut edge adds (1 − (−1))² = 4 to the sum and every other edge adds 0, so xTLx = 4 · (number of cut edges). Finding the best balanced cut this way is NP-hard. So we cheat: let xi take any real value, require x to have unit length, and keep it orthogonal to the constant vector (so it can't just put everything in one group). The best x under these rules is the eigenvector of λ2, the Fiedler vector. Round it back by its signs and you get the split.
A hard counting problem became an eigenvalue problem. Below, the Fiedler vector finds the bridge between two communities without being told anything about them.
Nodes take blue or orange from the sign of their entry in the Fiedler vector. Click two nodes to add or remove the edge between them, or pick a preset.
- Smallest eigenvalues of L
- Zero eigenvalues = components
- Algebraic connectivity λ₂
- Edges cut by the split
Dashed orange edges cross the split. Watch λ₂ grow as you add bridges and drop to 0 when you remove the last one. The bars show each node's entry in the Fiedler vector.
Spectral Clustering
Spectral clustering turns this into a general method for data points, not just graphs:
- Build a similarity graph. Link each point to its nearest neighbors, or weight every pair by wij = exp(−‖xi − xj‖² / 2σ²).
- Compute the Laplacian and its k eigenvectors with the smallest eigenvalues.
- Stack them as the columns of an n × k matrix. Each row is now a new point in k dimensions.
- Run k-means on those rows.
Why bother? Plain k-means assumes round blobs. It fails on two interleaved half moons or a ring around a dot. The similarity graph only cares about who is close to whom, so it follows the shape of the data. In the eigenvector space, the clusters turn into tight, easy to separate blobs. In practice people often use a normalized Laplacian, which gives balanced cuts and plays well with uneven degrees.
The same matrix shows up in more places. The heat equation on a graph reads dx/dt = −Lx, so the Laplacian describes how things spread along edges, from rumors to heat. The matrix tree theorem counts spanning trees with one determinant of L. And a layer of a graph neural network is little more than H' = σ(ÂHW): a normalized adjacency matrix  mixes each node's features with its neighbors', and a learned matrix W transforms them. That is a sparse matrix product with a learned twist, close kin to the Jacobians that train it.
Graphs also help the other way around. Vector databases index millions of embeddings in HNSW graphs, where a search hops greedily from neighbor to neighbor towards the query.
Euler threw away the map and kept the graph. Write that graph as a matrix, and the eigenvalues tell you how many pieces it has, how tightly they hold together, and where to cut.