Mathwords logoMathwords

Multigraph — Definition, Formula & Examples

A multigraph is a graph in which two vertices can be joined by more than one edge. These repeated connections are called parallel (or multiple) edges.

A multigraph is a triple G=(V,E,φ)G = (V, E, \varphi). Here VV is a set of vertices and EE is a set of edges. The map φ\varphi assigns each edge an unordered pair {u,v}\{u, v\} of distinct vertices, and φ\varphi need not be injective, so distinct edges may share the same endpoints. Conventions vary. In many texts, such as Rosen's *Discrete Mathematics*, a multigraph forbids loops, and a graph that allows both loops and parallel edges is called a pseudograph. Other authors allow loops in multigraphs.

Key Formula

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|
Where:
  • deg⁡(v)\deg(v) = Degree of vertex vv: the number of edges that touch vv, with each parallel edge counted separately
  • ∣E∣|E| = Total number of edges, with every parallel edge counted
  • VV = The set of vertices

Worked Example

Problem: The Königsberg bridge problem can be modeled as a multigraph. It has 4 land masses (vertices A, B, C, D) and 7 bridges (edges). A is joined to B by 2 bridges, to C by 2 bridges, and to D by 1 bridge. B and C are each joined to D by 1 bridge. Verify the handshaking lemma, then decide whether you can walk across every bridge exactly once.
Step 1: Find each degree, counting parallel edges separately. A touches 2 + 2 + 1 bridges. B, C, and D each touch 3 bridges.
deg⁡(A)=5,deg⁡(B)=deg⁡(C)=deg⁡(D)=3\deg(A)=5,\quad \deg(B)=\deg(C)=\deg(D)=3
Step 2: Add the degrees and compare the sum with twice the number of edges.
5+3+3+3=14=2(7)5+3+3+3 = 14 = 2(7)
Step 3: A connected multigraph has an Euler path only if it has 0 or 2 vertices of odd degree. Here all 4 vertices have odd degree, and 4 > 2.
#{odd-degree vertices}=4>2\#\{\text{odd-degree vertices}\} = 4 > 2
Answer: The degree sum is 14, which equals 2 × 7, so the handshaking lemma holds. Because all 4 vertices have odd degree, no walk crosses every bridge exactly once.

Why It Matters

Euler's 1736 solution to the Königsberg problem needed parallel edges, so multigraphs sit at the origin of graph theory and of Euler-circuit questions in discrete math courses. They also model road or flight networks with several routes between two cities, and molecules where atoms share double bonds.

Common Mistakes

Mistake: Applying the simple-graph bound of at most n(n−1)2\frac{n(n-1)}{2} edges to a multigraph.
Correction: That bound assumes each pair of vertices has at most one edge. A multigraph can have any number of parallel edges, so its edge count has no upper limit set by nn.

Related Terms