Multigraphs: Parallel Edges and Distinct Paths

A road map can contain two roads between the same towns. An airline can schedule several flights between the same airports. A payment network can record many transfers from one account to another. If we replace each of these collections by a single edge, we preserve reachability but destroy capacity, redundancy, frequency, identity, and often cost. The appropriate mathematical object is a multigraph, a graph in which two vertices may be joined by more than one edge.

Probably the most important artifact for artificial intelligence memory. Even though most researchers, and the entire technical media, have yet to realize it.

That small change forces a surprisingly important question: when are two paths different? Figure 1 exposes the ambiguity. The vertex sequence $v_0,v_1,v_3$ looks unique, yet it has two realizations if $v_0$ and $v_1$ are joined by edges $e_0$ and $e_1$. A search algorithm that records only the next vertex cannot tell those realizations apart. Sometimes that is exactly what we want. Sometimes it is a modeling error.

Figure 1: Collapsing parallel edges preserves the vertex sequence but erases the two edge-instance paths that realize it.

We will build the subject from definitions rather than treating parallel edges as an awkward exception.

One verified four-vertex multigraph will accompany us through matrices, shortest paths, cuts, Euler trails, random walks, graph neural networks, and a complete C++23 implementation. Three interactive laboratories expose the same data from different angles. Every major conceptual section ends with five fully solved exercises, for a total of $65$.

Cover the solutions and try each problem first: the article then becomes a compact course rather than a passive tour. Like everything on this blog, this article was created for you to learn, not for you to read. There is a difference. Understand this difference and win.

1. Why one edge is sometimes not enough

A simple graph permits at most one undirected edge $\{u,v\}$ for each unordered pair of distinct vertices. That model answers questions such as can $u$ reach $v$? efficiently, but it asserts that all direct connections between the pair can be represented by one fact. Real systems frequently violate that assertion.

Consider a transport network. Two bridges may connect the same banks, or two bus services may connect the same stops. The endpoints agree, but the bridge identities, capacities, tolls, and failure modes do not. In an airline network, morning and evening flights connect the same airports while carrying different departure times, fares, and aircraft. In a financial ledger, each transfer is an event with its own amount and timestamp. In a communication network, parallel physical links increase available bandwidth and provide redundancy. Collapsing these edges into one unweighted edge preserves only the weakest statement: some connection exists. The weakest statement rarely describes or solves the problem.