A multigraph is a type of graph in mathematics that allows more than one edge between the same pair of points. In a standard (simple) graph, any two points can be connected by at most one edge. A multigraph removes that restriction, letting you draw two, three, or any number of edges between the same two points. This small change opens up a much richer way to model real-world systems where multiple connections between the same locations or entities matter.
How a Multigraph Differs From a Simple Graph
In graph theory, a graph is built from two ingredients: a set of vertices (points) and a set of edges (connections between points). A simple graph has two rules. First, no two edges can share the same pair of endpoints, meaning there’s only one possible connection between any two vertices. Second, no edge can loop back to connect a vertex to itself (called a self-loop).
A multigraph relaxes the first rule. It allows multiple edges between the same pair of vertices while still forbidding self-loops. These repeated connections are called “parallel edges” or “multiple edges.” If you also allow self-loops on top of multiple edges, the structure is typically called a pseudograph, though some textbooks use “multigraph” loosely to include loops as well. The distinction matters when you’re reading formal definitions, so it’s worth checking which convention a particular source follows.
A Quick Visual Example
Imagine two cities, A and B, connected by a highway. In a simple graph, you’d draw one edge between A and B. But in reality, there might be three different routes between those cities: a highway, a coastal road, and a toll road. A multigraph lets you represent all three as separate edges between the same two vertices. Each edge is its own object with its own identity, even though both of its endpoints are the same.
The Formal Definition
Mathematically, a multigraph is defined as a triple (V, E, φ), where V is a finite set of vertices, E is a finite set of edges, and φ is a function that maps each edge to a pair of vertices. In a simple graph, you can get away with defining edges as just pairs of vertices, because there’s never more than one edge per pair. In a multigraph, you need that extra function φ to keep track of which edge is which, since several different edges might connect the same two vertices.
This is the key structural difference. The edge set E in a multigraph is essentially a multiset, meaning it can contain “duplicates” in the sense that multiple edges map to the same vertex pair. The degree of a vertex, which measures how connected it is, simply counts every edge touching that vertex, including all parallel edges. So if vertex A has three separate edges connecting it to vertex B and one edge connecting it to vertex C, vertex A has a degree of four.
Directed Multigraphs
When you add direction to the edges, turning each connection into a one-way arrow, you get a directed multigraph. This allows multiple arrows between the same pair of vertices, potentially pointing in different directions. In abstract algebra, directed multigraphs are often called quivers, and they play a surprisingly important role in advanced mathematics, particularly in representation theory where vector spaces are attached to each vertex and linear maps are assigned to each arrow.
For more practical purposes, directed multigraphs show up whenever you need to model systems where multiple distinct one-way relationships exist between the same two nodes. Think of two websites that link to each other through several different pages, or a pair of servers exchanging different types of network traffic.
Where Multigraphs Show Up in Practice
Multigraphs are the natural choice any time a simple graph would lose important information by collapsing parallel connections into one. Transportation networks are a classic example. Cities connected by multiple flight routes, bus lines, or roads are more accurately modeled as multigraphs, because each route may have different costs, travel times, or capacities. Research published in the European Journal of Operational Research demonstrated this directly: modeling a vehicle routing problem in Vienna as a multigraph instead of a simple graph led to significant distance savings, because the model could distinguish between multiple road options connecting the same intersections.
Communication networks also benefit from multigraph modeling. Two routers might be linked by several physical cables or logical channels, each carrying different traffic. In social network analysis, multigraphs capture the reality that two people can be connected through multiple types of relationships: coworkers, neighbors, and family members simultaneously, each represented by its own edge.
Electrical circuit design, parallel computing architectures, and even molecular biology (where atoms can form single, double, or triple bonds) all involve structures that map naturally onto multigraphs.
Why Not Just Use a Simple Graph?
You could always collapse multiple edges into a single edge and attach a number to it representing “how many” connections exist. This weighted-graph approach works for some problems, but it throws away the identity of individual edges. In a multigraph, each edge is a distinct object that can carry its own properties: a different route length, a different bandwidth, a different relationship type. When those individual properties matter for your analysis, a multigraph preserves information that a weighted simple graph does not.
Many graph algorithms designed for simple graphs need modification to work correctly on multigraphs. Counting paths, computing connectivity, and finding optimal routes all behave differently when parallel edges are present. The degree formula stays straightforward (count every edge touching a vertex), but algorithms that assume at most one edge per vertex pair can produce wrong answers if applied blindly to a multigraph.