Simple Graphs vs Multigraphs Explained

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Three definitions, two allowances

Two things a set of unordered pairs cannot express: an edge that joins a vertex to itself, and two distinct edges joining the same pair. Whether you permit them gives three different objects, and the names are worth getting right because theorems are stated about specific ones.

The simple graph is the default in most of the literature, and its definition is the one from the guide to vertices and edges:

G = (V, E)      with   E ⊆ [V]²      each edge is a 2-element subset of V

Because E is a set of 2-element subsets, {v, v} is not admissible (it has one element) and the same pair cannot appear twice (a set holds each element once). Both restrictions are consequences of the notation rather than decisions someone made.

To lift them you need a different formalism. Bondy and Murty's Graph Theory gives edges an identity of their own and adds a function saying which pair each one joins:

G = (V, E, ψ)      with   ψ: E → unordered pairs of (not necessarily distinct) vertices

Now e1 and e2 can be different elements of E with ψ(e1) = ψ(e2) = {u, v}, which is a pair of parallel edges, and ψ(e) = {v, v} is a loop. Diestel reaches the same place with two maps sending each edge to its ends, and West with a relation associating each edge with its endpoints. The formalism differs; the content does not.

Two warnings about the vocabulary itself, because they cause real confusion when reading papers:

• "Multigraph" is not used consistently. Some authors allow loops in a multigraph, others reserve that for "pseudograph", and a few use "multigraph" for any graph at all. Check the source's own definition before quoting one of its theorems.
• "Graph" usually means "simple graph". Most texts say so once in chapter one and then never repeat it. A result stated for "graphs" often has an unstated simplicity hypothesis, and section 5 shows how badly some of them fail without it.

2. Graph theory was founded on a multigraph

This is not a marginal case bolted on afterwards. The problem that started the subject is a multigraph, and it stops being the same problem if you simplify it.

Euler's 1736 paper on the bridges of Königsberg models four landmasses joined by seven bridges. Two bridges connect the north bank to the island, and two more connect the south bank to the island. Those are parallel edges, and no simple graph can hold them.

Euler's criterion is about degree parity, and the parallel bridges are what push the degrees to where they are:

Königsberg multigraph      7 edges    degrees 3, 5, 3, 3    four odd  → no Eulerian trail
Underlying simple graph    5 edges    degrees 2, 3, 2, 3    two odd   → a trail exists

Delete the duplicates and the answer flips. The multiplicity is not decoration on the model, it is the model, and the historical detail in the history of graph theory is inseparable from the formalism. Anyone who loads the seven bridges into a data structure that silently deduplicates edges will conclude that Euler was wrong.

3. What a loop does to degree

Degree counts edge ends meeting a vertex, not edges. A loop has two ends and both of them land on the same vertex, so:

A loop at v contributes 2 to deg(v). Parallel edges each contribute 1, exactly as separate edges do.

That convention is forced, not chosen. The handshaking lemma counts the pairs (vertex, edge end at it) two ways, and every edge including a loop has exactly two ends, so ∑ deg(v) = 2m holds for pseudographs unchanged. Give a loop degree 1 and the oldest theorem in the subject breaks immediately.

Some consequences worth having in mind:

• A vertex with a loop and no other edges has degree 2, not 0, and is not isolated.
• The number of odd-degree vertices is still even, since the proof only uses ∑ deg(v) = 2m.
• In a simple graph deg(v) = |N(v)|, the size of the neighbourhood. In a multigraph that identity fails: three parallel edges to one neighbour give degree 3 and one neighbour. Code that computes degree as the length of a deduplicated neighbour set is computing the wrong number.

4. What multiplicity changes, and what it cannot

The useful question is not "is my graph simple" but "does the property I am computing depend on multiplicity". The answers split cleanly, and the split is not obvious.

Three of those rows deserve their reasoning spelled out.

Colouring ignores parallel edges but dies on loops. A proper colouring requires the ends of every edge to get different colours. A second copy of {u, v} repeats a constraint that is already there, so the set of proper colourings, and therefore the chromatic number and the chromatic polynomial, are exactly those of the underlying simple graph. A loop demands c(v) ≠ c(v), which nothing satisfies, so a pseudograph with a loop has no proper colouring at all and its chromatic polynomial is identically zero. This is why graph colouring is almost always stated for loopless graphs.

Spanning tree counts do depend on multiplicity. Two vertices joined by a single edge have one spanning tree; joined by two parallel edges they have two, because choosing either edge gives a different tree. Kirchhoff's matrix-tree theorem of 1847 counts them from the Laplacian, and it is stated for multigraphs precisely because the multiplicities enter the matrix as off-diagonal counts. Electrical networks, which is where Kirchhoff met the problem, routinely have components in parallel.

Cuts and flows depend on multiplicity. The minimum number of edges whose removal disconnects u from v is 1 when a single edge joins them and 2 when two do. Since max flow equals min cut, the same holds for flow: k parallel unit-capacity edges carry k units. This is exactly why a multigraph with unit capacities is the natural unweighted model of a flow network.

5. Every simple-graph bound stops holding

A large fraction of the standard results carry an unstated simplicity assumption, and they do not degrade gracefully without it. They fail outright.

The two rows that survive are worth noticing as much as the ones that fail. The handshaking lemma and Euler's polyhedral formula are both proved by counting incidences, and counting arguments do not care whether two edges happen to join the same pair. The bounds that fail are the ones proved by choosing distinct pairs of vertices, which is precisely the step a multigraph invalidates.

The practical version of this section: when you look up a bound, check whether its proof counts incidences or counts pairs. The first kind travels to multigraphs, the second does not.

6. Storage: where the adjacency matrix runs out

The three standard representations degrade very differently, and the differences decide which one you use.

The adjacency matrix stops being a 0/1 matrix. The natural extension holds the number of edges joining each pair, so entry (u, v) becomes a count, and a loop conventionally puts 2 on the diagonal so that row sums still give degrees. It works, but it has a fatal limitation for real data: a count cannot carry per-edge information. If your three parallel flights each have a different price, a matrix of counts has nowhere to put them.

simple       A[u][v] ∈ {0, 1}
multigraph   A[u][v] = number of edges joining u and v
pseudograph  A[v][v] = 2 × (number of loops at v)      so that row sums are degrees

The adjacency list keeps duplicates. The list for u simply contains v as many times as there are edges joining them. Traversal code is unchanged, and BFS or DFS will consider the same neighbour repeatedly, which is harmless when the visited check is on vertices.

The edge list becomes the natural format. This is the representation that actually fits the mathematics: each edge is a record with its own identity, so parallel edges are simply distinct records, and per-edge attributes have somewhere to live. That is the incidence-function definition of section 1 expressed as a data structure.

One design point follows, and it is the single most useful thing to take from this section:

In a multigraph, edges need identities. A pair of endpoints no longer identifies an edge, so anything that refers to an edge, whether a matching, a spanning tree, a flow or a deletion, must refer to an edge ID and not to (u, v).

Almost every multigraph bug traces back to that one sentence. Storing a spanning tree as a set of vertex pairs, or a visited-edge set keyed on (u, v), quietly conflates parallel edges and produces answers that are wrong in ways no type checker will catch.

7. Which algorithms care

Most traversal-shaped algorithms are indifferent to multiplicity, because they mark vertices. The ones that mark or select edges need attention.

The Karger row is the one that surprises people, and it is worth stating in full because it inverts the usual instinct. Karger's randomised minimum cut algorithm repeatedly contracts a uniformly random edge, merging its two endpoints into one vertex. Contraction turns two edges that pointed at the two merged vertices into two parallel edges pointing at the new one, and the algorithm's probability analysis depends on keeping every copy, because the chance of contracting an edge is proportional to how many copies there are. Simplify the intermediate graph and the algorithm stops being correct. The same is true of the contraction step in Borůvka's spanning tree algorithm.

8. When a multigraph is not optional

Multigraphs are not a curiosity to be normalised away. They are the honest model whenever two entities can be related more than once and the individual relations matter:

• Transport networks. Two cities joined by three different flights, or a road and a rail link between the same pair. Each has its own duration, price and capacity.
• Electrical circuits. Components in parallel between the same two nodes, which is exactly the setting where Kirchhoff developed the matrix-tree theorem in 1847.
• Transaction and payment graphs. Two accounts may transact many times; collapsing that into one edge loses amounts, timestamps and the count itself, which is usually the signal being looked for.
• Chemical reaction and molecular graphs. Double and triple bonds are parallel edges in the classical graph model of a molecule.
• Knowledge graphs and RDF. Two entities related by several distinct predicates. This is why such data is usually stored as triples, which is an edge list with a label per edge.
• Anything built by contraction. Karger's algorithm, Borůvka's algorithm, and the condensation steps inside many approximation algorithms all create parallel edges as they run, whatever the input was.
• Eulerian route problems. Street sweeping and postal routes need every physical street traversed, and two streets between the same junctions are two obligations.

9. Simplifying, and what it costs

Turning a multigraph into a simple graph is often the right move, and it is only safe if you know which of the properties in section 4 you are about to change. There are three standard ways, and they answer different questions:

Note that the second and third rules are incompatible: summing is right for capacities and wrong for distances, taking the minimum is right for distances and wrong for capacities. Which one applies depends on how weights combine along a path, which is the subject of the companion guide on weighted vs unweighted graphs. Choosing the wrong collapse silently answers a different question, and the graph will look perfectly reasonable afterwards.

A fourth option is often better than any of them: keep the multigraph and let the algorithm handle it. BFS, DFS, Dijkstra, Kruskal and Prim all run correctly on multigraphs as they stand, so simplification frequently buys nothing and costs information.

10. Directed multigraphs

Everything above transfers to directed graphs, with one extra distinction worth naming. In a digraph, the arcs (u, v) and (v, u) are already different objects, which is not multiplicity but direction: that pair is a digon, and an ordinary digraph is already allowed to contain one without any extension to its definition. Plenty of digraphs contain none at all: a DAG never does. Multiplicity in the directed setting means two or more arcs with the same tail and the same head, which again needs an incidence-style definition, as in Bang-Jensen and Gutin's Digraphs.

The practical consequences carry over directly: in-degree and out-degree count arcs rather than distinct neighbours, a directed loop adds 1 to both, and Eulerian conditions on a directed multigraph still compare in-degree with out-degree at every vertex.

11. Common mistakes

• Loading a multigraph into a structure that deduplicates. A Set of pairs, an adjacency matrix of booleans or a database unique constraint on (u, v) all silently discard parallel edges. The graph then looks fine and every count is wrong.
• Identifying edges by their endpoints. In a multigraph (u, v) names a set of edges, not one. Matchings, spanning trees, flows and visited-edge sets must key on edge IDs.
• Computing degree as the neighbour count. Correct in a simple graph, wrong the moment an edge is duplicated or a loop appears.
• Giving a loop degree 1. It contributes 2, and the handshaking lemma depends on it.
• Applying m ≤ n(n-1)/2. That bound, and everything derived from it including sparse-versus-dense reasoning, needs simplicity.
• Simplifying before an Eulerian, cut or flow computation. All three depend on multiplicity, as Königsberg demonstrates on the founding example of the subject.
• Deduplicating inside a contraction algorithm. Karger's and Borůvka's algorithms create parallel edges deliberately and need them kept.
• Assuming a library does what you expect. Graph libraries differ on whether adding an existing edge creates a duplicate, is ignored, or raises. Check, once, in a test.

12. Glossary

14. References

The definitions, theorems and attributions above come from these sources, listed in chronological order.

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8 (published 1741), 128 to 140. The Königsberg bridges, modelled as a multigraph.
2. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird." Annalen der Physik 148(12), 497 to 508. The matrix-tree theorem, developed on electrical networks with parallel components.
3. Harary, F. (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley. Distinguishes graphs, multigraphs and pseudographs.
4. Karger, D. R. (1993). "Global Min-cuts in RNC, and Other Ramifications of a Simple Min-cut Algorithm." Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 21 to 30. The contraction algorithm that creates parallel edges as it runs.
5. Karger, D. R. and Stein, C. (1996). "A New Approach to the Minimum Cut Problem." Journal of the ACM 43(4), 601 to 640.
6. Bollobás, B. (1998). Modern Graph Theory. Graduate Texts in Mathematics 184. New York: Springer.
7. West, D. B. (2001). Introduction to Graph Theory, 2nd edition. Upper Saddle River: Prentice Hall. Defines a graph by a vertex set, an edge set and an endpoint relation, which admits loops and parallel edges.
8. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer. Source of the incidence-function definition in section 1.
9. Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications, 2nd edition. London: Springer. Directed multigraphs.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition. Cambridge, Massachusetts: MIT Press.
11. Wilson, R. J. (2010). Introduction to Graph Theory, 5th edition. Harlow: Prentice Hall. Develops multigraphs alongside simple graphs from the first chapter.
12. Chartrand, G., Lesniak, L. and Zhang, P. (2015). Graphs & Digraphs, 6th edition. Boca Raton: CRC Press.
13. Diestel, R. (2017). Graph Theory, 5th edition. Graduate Texts in Mathematics 173. Berlin: Springer. Source of the simple-graph definition and of the multigraph formulation with two end maps.