Chapter 23. Multigraphs

A multigraph is a graph that allows more than one edge between the same pair of vertices. These repeated edges are called parallel edges or multiple edges. This differs from a simple graph, where at most one edge may join any two distinct vertices.

Multigraphs are useful when one connection between two vertices is not enough to describe the system. Two cities may have several roads between them. Two airports may have several flights on the same route. Two people may have several different kinds of relationships. Two states in an automaton may have several transitions with different labels.

23.1 Definition

An undirected multigraph may be written as

G = (V,E),

where $V$ is a set of vertices and $E$ is a multiset of unordered pairs of vertices.

The word multiset is important. A set cannot contain the same element more than once. A multiset can.

Thus the edge multiset may contain

\{u,v\}, \{u,v\}, \{u,v\}.

This means that three parallel edges join $u$ and $v$ .

A more precise definition treats edges as objects with endpoint maps. In this form,

G = (V,E,\phi),

where $V$ is a set of vertices, $E$ is a set of edge objects, and

\phi : E \to \{\{u,v\}: u,v \in V\}

assigns endpoints to each edge.

This second definition is often better because two parallel edges may have distinct identities, labels, weights, capacities, or meanings. Standard references distinguish these two conventions: either edges are repeated endpoint pairs, or edges are separate objects assigned to endpoint pairs.

23.2 Parallel Edges

Two edges are parallel if they have the same endpoints.

\phi(e_1)=\{u,v\}

and

\phi(e_2)=\{u,v\},

with

e_1 \neq e_2,

then $e_1$ and $e_2$ are parallel edges.

For example, suppose

V=\{a,b,c\}

and

E=\{e_1,e_2,e_3\}

with

\phi(e_1)=\{a,b\}, \qquad \phi(e_2)=\{a,b\}, \qquad \phi(e_3)=\{b,c\}.

Then $e_1$ and $e_2$ are parallel edges between $a$ and $b$ . The graph is a multigraph because a simple graph would allow only one edge between $a$ and $b$ .

23.3 Loops and Pseudographs

A loop is an edge whose two endpoints are the same vertex:

\phi(e)=\{v,v\}.

Different authors use different conventions. Some allow loops in multigraphs. Others reserve the word multigraph for graphs with parallel edges but no loops, and use pseudograph for a multigraph that also allows loops. The convention should be stated before theorems are applied.

In this book, unless stated otherwise, a multigraph may have parallel edges. Loops will be mentioned explicitly when they are allowed.

This convention avoids ambiguity. Many theorems have slightly different degree counts or path conditions when loops are present.

23.4 Simple Graphs as Special Multigraphs

Every simple graph is a multigraph with no parallel edges and no loops.

Thus multigraphs generalize simple graphs.

The difference lies in the edge structure. In a simple graph, the edge $\{u,v\}$ either exists or does not exist. In a multigraph, several distinct edges may share the same endpoints.

For example, a simple graph may contain

\{a,b\}.

A multigraph may contain

e_1 : \{a,b\}, \qquad e_2 : \{a,b\}, \qquad e_3 : \{a,b\}.

The vertices are the same. The endpoint pair is the same. The edge identities differ.

23.5 Multiplicity

The multiplicity of a pair of vertices is the number of edges joining them.

For distinct vertices $u$ and $v$ , define

m(u,v) = |\{e \in E : \phi(e)=\{u,v\}\}|.

If $m(u,v)=0$ , then $u$ and $v$ are not adjacent.

If $m(u,v)=1$ , then there is exactly one edge between them.

m(u,v) > 1,

then $u$ and $v$ are joined by parallel edges.

In a simple graph,

m(u,v) \in \{0,1\}

for every pair of distinct vertices. In a multigraph, $m(u,v)$ may be any nonnegative integer.

23.6 Degree in a Multigraph

The degree of a vertex in a multigraph counts incident edges with multiplicity.

If three parallel edges join $u$ and $v$ , then all three contribute to the degree of $u$ , and all three contribute to the degree of $v$ .

For a vertex $v$ , the degree is

\deg(v) = |\{e \in E : v \text{ is incident with } e\}|,

with parallel edges counted separately.

If loops are allowed, the usual convention is that a loop contributes $2$ to the degree of its incident vertex. This convention preserves the handshaking identity.

For finite undirected multigraphs,

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

Each non-loop edge contributes $1$ to the degree of each of its two endpoints. A loop contributes $2$ to the degree of its single endpoint. Therefore every edge contributes $2$ to the total degree count.

23.7 Example of Degree Counting

Let

V=\{a,b,c\}

and let the edges be

e_1:\{a,b\}, \qquad e_2:\{a,b\}, \qquad e_3:\{a,c\}, \qquad e_4:\{b,c\}.

There are two parallel edges between $a$ and $b$ .

The degrees are:

\deg(a)=3,

because $e_1,e_2,e_3$ are incident with $a$ .

\deg(b)=3,

because $e_1,e_2,e_4$ are incident with $b$ .

\deg(c)=2,

because $e_3,e_4$ are incident with $c$ .

Thus

\deg(a)+\deg(b)+\deg(c)=3+3+2=8.

There are four edges, so

2|E|=2\cdot 4=8.

The handshaking identity holds.

23.8 Adjacency in Multigraphs

In a simple graph, adjacency is a yes-or-no relation. Vertices $u$ and $v$ are adjacent if an edge joins them.

In a multigraph, adjacency still means that at least one edge joins the vertices. But the number of edges is also important.

Thus we distinguish:

Concept	Meaning
Adjacent	at least one edge joins the vertices
Multiplicity	number of edges joining the vertices
Parallel edges	distinct edges with the same endpoints

For many structural questions, simple adjacency is enough. For flow, routing, reliability, and enumeration, multiplicity matters.

23.9 Walks, Trails, Paths, and Cycles

Walks, trails, paths, and cycles are defined in multigraphs much as they are in simple graphs, but edge identity must be handled carefully.

A walk may use vertices and edges in sequence:

v_0,e_1,v_1,e_2,\ldots,e_k,v_k,

where each edge $e_i$ joins $v_{i-1}$ and $v_i$ .

This notation is useful in multigraphs because the vertex sequence alone may not determine the edge sequence. If two vertices are joined by several parallel edges, then moving from $u$ to $v$ can be done through several distinct edges.

A trail is a walk with no repeated edge.

A path is a walk with no repeated vertex, except where a cycle convention allows the first and last vertices to agree.

A cycle is a closed path, again with attention to edge identities.

For example, if $u$ and $v$ are joined by two parallel edges $e_1$ and $e_2$ , then

u,e_1,v,e_2,u

is a closed trail of length $2$ , provided both edges are distinct. Such a structure cannot occur in a simple graph with only two vertices and no loops.

23.10 Underlying Simple Graph

Every multigraph has an underlying simple graph.

The underlying simple graph is obtained by replacing every nonzero multiplicity between two distinct vertices by a single edge and usually deleting loops.

Formally, the underlying simple graph has vertex set $V$ , and it contains the edge $\{u,v\}$ when $u \neq v$ and

m(u,v) \geq 1.

This operation loses information. It forgets how many parallel edges existed and forgets edge identities, labels, and weights.

For example, if a multigraph has five roads between two cities, the underlying simple graph records only that the cities are connected.

The underlying simple graph is useful when only reachability or ordinary adjacency matters. It is insufficient when multiplicity carries meaning.

23.11 Converting a Multigraph to a Simple Graph

There are several ways to replace a multigraph by a simple graph.

The simplest method is to take the underlying simple graph. Parallel edges are merged into one edge.

Another method subdivides edges. Each edge $e$ joining $u$ and $v$ is replaced by a new vertex $x_e$ and two edges

u-x_e, \qquad x_e-v.

This preserves edge identity by turning each original edge into its own intermediate vertex.

For example, two parallel edges between $u$ and $v$ become two distinct length-two paths through two distinct new vertices.

The correct conversion depends on the problem. Merging edges preserves coarse adjacency. Subdivision preserves more incidence information.

23.12 Directed Multigraphs

A directed multigraph, also called a multidigraph, allows multiple arcs with the same source and target.

It may be written as

D=(V,A),

where $A$ is a multiset of ordered pairs of vertices.

Alternatively, with arc identities,

D=(V,A,s,t),

where $A$ is a set of arcs and

s:A\to V

assigns to each arc its source, while

t:A\to V

assigns to each arc its target. This identity-based definition is common when parallel arcs need separate labels, weights, or data.

Two arcs $a_1$ and $a_2$ are parallel if

s(a_1)=s(a_2)

and

t(a_1)=t(a_2).

Opposite arcs are not parallel in this directed sense. An arc from $u$ to $v$ and an arc from $v$ to $u$ have different ordered endpoints.

23.13 Adjacency Matrices for Multigraphs

For a simple graph, an adjacency matrix usually has entries $0$ or $1$ . For a multigraph, the adjacency matrix records multiplicities.

Let

V=\{v_1,\ldots,v_n\}.

The adjacency matrix $M$ of an undirected multigraph may be defined by

M_{ij}=m(v_i,v_j)

for $i\neq j$ .

Thus $M_{ij}$ is the number of edges between $v_i$ and $v_j$ . This is the standard adjustment needed when representing multigraphs by matrices.

For a directed multigraph,

M_{ij}

is the number of arcs from $v_i$ to $v_j$ .

If loops are allowed, diagonal entries record loops, though conventions differ on whether a loop contributes $1$ or $2$ to diagonal degree calculations. The convention should be stated explicitly.

23.14 Incidence Matrices for Multigraphs

The incidence matrix is often more natural for multigraphs than the adjacency matrix.

Let

G=(V,E,\phi)

be an undirected multigraph with

V=\{v_1,\ldots,v_n\}

and

E=\{e_1,\ldots,e_m\}.

The incidence matrix $B$ has one row for each vertex and one column for each edge.

For a non-loop edge $e_j$ joining $u$ and $v$ , the column for $e_j$ has a $1$ in the rows for $u$ and $v$ , and $0$ elsewhere.

Parallel edges receive different columns. Thus their identities are preserved.

For directed multigraphs, one may use the signed incidence convention:

B_{ij} = \begin{cases} -1, & \text{if } v_i \text{ is the source of } e_j, \\ 1, & \text{if } v_i \text{ is the target of } e_j, \\ 0, & \text{otherwise.} \end{cases}

This representation is important in flow networks and algebraic graph theory.

23.15 Edge Labels and Attributes

Multigraphs are especially useful when edges carry labels or attributes.

Suppose two cities $u$ and $v$ are connected by three transportation routes:

e_1 = \text{road}, \qquad e_2 = \text{rail}, \qquad e_3 = \text{flight}.

All three edges have the same endpoints, but they represent different relations.

A simple graph would collapse these into one connection and lose the distinction. A multigraph keeps them separate.

Edge attributes may include:

Attribute	Example
Label	road, rail, flight
Weight	cost or distance
Capacity	maximum flow
Time	travel duration
Reliability	probability of success
Type	friendship, message, transaction
Identifier	unique edge id

This is why many graph software libraries use multigraph structures when several relationships may exist between the same nodes. For example, NetworkX describes its MultiGraph class as an undirected graph class that can store multiple edges between two nodes, with optional edge data.

23.16 Applications

Multigraphs model systems where two vertices may be connected in more than one way.

Application	Vertices	Parallel edges represent
Transportation	cities or stations	multiple routes
Airline networks	airports	multiple flights
Communication networks	devices	multiple channels
Electrical networks	junctions	parallel wires
Social networks	people	different relationship types
Knowledge graphs	entities	multiple relations
Automata	states	different transitions
Databases	records	multiple foreign-key relations
Flow networks	locations	separate capacity channels

In each case, replacing the multigraph by a simple graph may discard essential information.

23.17 Multigraphs and Flow

Parallel edges occur naturally in flow networks.

Suppose two vertices $u$ and $v$ are connected by two pipes, one with capacity $5$ and one with capacity $8$ . As a multigraph, these are two distinct edges:

e_1:\{u,v\}, \quad c(e_1)=5,

e_2:\{u,v\}, \quad c(e_2)=8.

One may combine them into a single edge of capacity $13$ if the only concern is total capacity between $u$ and $v$ . But this combination loses edge-level information.

If the two pipes have different costs, risks, failure probabilities, or control rules, they should remain separate.

Thus multigraphs allow models to preserve physical or semantic edge identity.

23.18 Multigraphs and Eulerian Theory

Eulerian theory often becomes more natural in multigraphs.

An Eulerian trail uses every edge exactly once. If several parallel edges join the same pair of vertices, each must be used separately.

For example, two vertices joined by two parallel edges form a closed Eulerian trail:

u,e_1,v,e_2,u.

This trail uses both edges exactly once. The underlying simple graph would have only one edge and would not represent the same traversal problem.

The degree condition for Eulerian circuits still uses edge multiplicity. In an undirected multigraph, every vertex with nonzero degree must lie in one connected component, and every vertex must have even degree.

Parallel edges contribute separately to these degrees.

23.19 Common Mistakes

A common mistake is to treat parallel edges as one edge. This changes degrees, trail counts, cut sizes, flow capacities, and reliability calculations.

Another mistake is to forget edge identity. In a multigraph, an edge may need its own label, weight, or id, even when its endpoints match another edge.

A third mistake is to apply simple graph matrix conventions without modification. A multigraph adjacency matrix should record multiplicity, not just presence or absence.

A fourth mistake is to ignore the loop convention. Some authors allow loops in multigraphs, while others separate them into pseudographs. Always check the convention.

23.20 Summary

A multigraph is a graph that permits multiple edges between the same pair of vertices. These edges are called parallel edges. A multigraph may be defined using a multiset of endpoint pairs or by treating edges as separate objects with an endpoint map.

Multiplicity counts how many edges join two vertices. Degree counts incident edges with multiplicity. The adjacency matrix records edge counts rather than only $0$ or $1$ . The incidence matrix gives each edge its own column and therefore preserves edge identity.

Multigraphs are necessary when multiple relationships, routes, capacities, labels, or interactions can occur between the same pair of vertices. They extend simple graphs while preserving the same basic language of vertices, edges, walks, trails, paths, cycles, and connectivity.