Graphs: A Language for Relationships

A graph $G = (V, E)$ is a set of vertices and a set of edges joining pairs of them. That is the entire definition, and its poverty is the point: nothing in it mentions distance, position, or what the vertices represent.

Definition: Edges are undirected when the relation is symmetric (friendship, adjacency) and directed when it is not (following, dependency, one-way streets). They are weighted when each carries a number: distance, capacity, cost, probability.

Because the definition assumes so little, a theorem about graphs applies to every domain that fits the shape. "Find the cheapest route" and "find the least-error decoding of a message" and "find the most likely sequence of hidden states" are the same shortest-path problem, and one algorithm solves all three.

The degree of a vertex is how many edges meet it. Summing degrees over all vertices counts every edge exactly twice, once from each end:

$\sum_{v \in V} \deg(v) = 2|E|$

That is the handshake lemma, and a corollary follows immediately: since the total is even, the number of odd-degree vertices must be even. You cannot build a graph with exactly three odd-degree vertices, however hard you try.

Key idea: This is what a graph-theoretic argument looks like. No algorithm ran, no case was checked, and the conclusion holds for every graph that will ever exist. Counting one quantity two different ways is the most productive single technique in combinatorics, and it settles the Konigsberg question later in this lesson.

A graph on $n$ vertices has at most $\binom{n}{2}$ edges, and that ceiling grows quadratically.

Real graphs land nowhere near that ceiling. A social network with a billion users averages a few hundred friends each, so $|E|$ is a small multiple of $|V|$, not $|V|^2$. This is not a detail: it decides how you store the thing.

A million-vertex matrix is $10^{12}$ entries. The same graph at average degree 10 is about $10^7$ list entries, a factor of 100,000.

A tree is a connected graph with no cycles, and it is rigid in a way that makes it easy to reason about. Three properties characterise it, and any two imply the third:

• connected
• acyclic
• exactly $|V| - 1$ edges

Remove any edge and it disconnects; add any edge and it creates exactly one cycle. There is exactly one path between any two vertices, which is why file systems, org charts, parse trees and B-trees all take this shape when you want lookup without ambiguity.

Try it: Count the edges in any tree you can see, a directory listing, a family tree, a JSON document. It will be one fewer than the nodes, every time. If it is not, the structure has a cycle in it and is not a tree, which for a filesystem means a symlink loop and for a JSON document means it was not really JSON.

A directed acyclic graph has directed edges and no way to follow them back to where you started. That single restriction is what makes build systems, spreadsheets, task schedulers and version-control histories tractable: it guarantees a linear order consistent with every edge, called a topological order. Here ast.h must be processed before the three objects that include it, and all three before the link step, but their order among themselves is free.

That if-and-only-if is what makes the technique useful. The algorithm does not merely fail to find an order, it certifies that none exists, and hands you the offending vertices as a by-product.

In practice: When a tool says "circular dependency detected", it usually already knows which nodes are involved, because they are precisely the ones left over when the sort stalls. Ask it to print them.

A graph is bipartite when its vertices split into two sides with every edge crossing between them. Users and items, jobs and machines, students and courses, applicants and posts: the structure shows up wherever two kinds of thing relate to each other but not among themselves.

It has a clean characterisation. A graph is bipartite if and only if it contains no cycle of odd length. The reason is a two-colouring argument: walk the graph alternating colours, and you succeed unless some cycle forces a vertex to be both.

from collections import deque

def bipartite(adj, start):
    side = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in side:
                side[v] = 1 - side[u]
                q.append(v)
            elif side[v] == side[u]:
                return False        # an odd cycle closed here
    return True

Matching problems on bipartite graphs are solvable in polynomial time, while the same questions on general graphs get much harder, which is why identifying the structure is worth the check.

Assign a colour to each vertex so no edge joins two of the same colour. The minimum number needed is the chromatic number, and a startling range of scheduling problems is exactly this question.

• Register allocation. Vertices are variables, edges join variables live at the same time, colours are CPU registers. A valid colouring is a valid assignment; running out of colours is a spill to memory.
• Exam timetabling. Vertices are exams, edges join exams sharing a student, colours are time slots.
• Frequency assignment. Vertices are transmitters, edges join those close enough to interfere, colours are channels.

Deciding whether three colours suffice is NP-complete in general, so compilers use fast heuristics rather than optimal colourings, and accept the occasional unnecessary spill.

Planar graphs, those drawable without crossings, are the famous exception: four colours always suffice. Appel and Haken proved it in 1976 by reducing the problem to 1,936 configurations and checking them by computer, the first major theorem to be settled that way, and a proof no human has ever read in full.

Konigsberg had seven bridges over the Pregel, and its residents wanted a walk crossing each exactly once. Euler answered it in 1736 by throwing away the map: only the connection pattern mattered.

His criterion is a counting argument. Any vertex you pass through uses two edges, one in and one out, so all interior vertices need even degree; only the start and end may be odd. Konigsberg's four landmasses had degrees 3, 3, 3 and 5, all odd, so no such walk exists. The proof took a paragraph and founded a field.

Key idea: Those two questions sound like variations on each other, and one is a degree check while the other is among the hardest problems we know. Nothing in the phrasing warns you which is which. Recognising the structure of a problem, rather than its wording, is what this lesson is for.

The hard part is rarely the algorithm. It is deciding what the vertices are, and a bad choice makes an easy problem look impossible.

1. What is a vertex? Often not the obvious noun. For routing with time-dependent traffic, a vertex is a place and a time, not a place.
2. What is an edge, and is it directed? Ask whether the relation is symmetric. Getting this wrong silently doubles or halves your answer.
3. Does an edge carry a number? Weight turns "is it reachable" into "what does it cost", a different class of algorithm.
4. Which special family is it in? Tree, DAG, bipartite and planar each unlock methods unavailable in general, so it pays to check before reaching for a general-purpose solver.
5. Is it sparse? It almost certainly is, which decides the representation and often the practical running time more than the algorithm does.

The rest is looking up which algorithm applies, and the structure you identified in step 4 is what tells you which one that is.