Graph Theory Basics

A prime broker wants to know: if Counterparty A defaults, which other counterparties are exposed through shared collateral chains, and how many steps away is the contagion? Answering this needs a way to represent "who is connected to whom" that's separate from any specific numbers — just the pattern of connections. Graph theory is exactly that vocabulary: a small set of definitions for talking about things (nodes) and the connections between them (edges), general enough to describe counterparty networks, correlation structures between assets, or the flow of orders through an exchange.

An analogy: a subway map

A subway map is a graph in disguise: stations are nodes, and the tracks connecting adjacent stations are edges. You don't need to know the physical distance or travel time to reason about basic structure — which stations are reachable from which, how many transfers a trip requires, whether the network has a single connected system or several isolated islands. Graph theory strips a network down to exactly this bare connectivity structure, then builds precise tools on top of it.

The vocabulary, one piece at a time

A graph $G = (V, E)$ consists of a set of vertices (or nodes) $V$ — the things being connected — and a set of edges $E$, each edge a pair of vertices that are linked. If edges have a direction (A owes B, not necessarily the reverse), the graph is directed; otherwise it's undirected. The degree of a vertex is the number of edges touching it — how many direct connections it has. A path is a sequence of edges connecting one vertex to another through intermediate vertices, and the shortest path between two vertices is the path using the fewest edges (or, if edges carry weights like cost or distance, the path with the smallest total weight). A graph is connected if every vertex can reach every other vertex via some path; if not, it splits into separate connected components — isolated islands with no path between them.

A graph can be stored as an adjacency matrix $A$, an $n \times n$ grid where $A_{ij} = 1$ if an edge connects vertex $i$ and vertex $j$, and $0$ otherwise (for a weighted graph, $A_{ij}$ holds the edge's weight instead of just $0$/$1$). In plain English: row $i$ of the matrix is a complete list of who vertex $i$ is directly connected to, turning a picture of a network into a table of numbers that algorithms and linear algebra can operate on directly.

Worked example 1: counting components and paths by hand

Five trading desks (A, B, C, D, E) share collateral agreements: A–B, B–C, D–E. As a graph, vertices are the desks and edges are shared agreements. Degree of B is 2 (connected to A and C); degree of D is 1. There are two connected components: $\{A, B, C\}$ and $\{D, E\}$ — a shock hitting D can propagate to E but never reach A, B, or C, because there's no path between the two islands. The shortest path from A to C is A–B–C, length 2 (two edges), even though there's no direct A–C edge.

Worked example 2: the adjacency matrix by hand

For the same five desks in order A, B, C, D, E, the adjacency matrix is:

$$A = \begin{pmatrix} 0&1&0&0&0 \\ 1&0&1&0&0 \\ 0&1&0&0&0 \\ 0&0&0&0&1 \\ 0&0&0&1&0 \end{pmatrix} .$$

Row A has a 1 only in column B, matching "A connects only to B." The block-diagonal structure — zeros everywhere connecting the $\{A,B,C\}$ block to the $\{D,E\}$ block — is a direct visual signature of the two disconnected components.

What this means in practice

Graph theory underlies counterparty and systemic risk mapping (who is exposed to whom, and how far a default propagates), correlation network analysis for spotting clusters of co-moving assets, order-routing and market-microstructure questions phrased as shortest-path or flow problems, and any "who's connected to whom" question that shows up in coding interviews as breadth-first search or connected-components problems. The core payoff is that once a relationship is represented as a graph, a large toolkit of well-understood algorithms — shortest path, connectivity, clustering — becomes directly applicable.