# Definition:Multigraph

## Contents

## Definition

A **multigraph** is a graph that can have more than one edge between a pair of vertices.

That is, $G = \left({V, E}\right)$ is a **multigraph** if $V$ is a set and $E$ is a multiset of 2-element subsets of $V$.

The graph above is a **multigraph** because of the double edge between $B$ and $C$ and the triple edge between $E$ and $F$.

### Multiple Edge

Let $G = \struct {V, E}$ be a multigraph.

A **multiple edge** is an edge of $G$ which has another edge with the same endvertices.

That is, where there is more than one edge that joins any pair of vertices, each of those edges is called a multiple edge.

### Simple Edge

Let $G = \struct {V, E}$ be a multigraph.

A **simple edge** is an edge $u v$ of $G$ which is the only edge of $G$ which is incident to both $u$ and $v$.

## Multiplicity

The **multiplicity** of a multigraph is the maximum multiplicity of its (multiple) edges.

The multiplicity of the above example is $3$.

## Also defined as

Some sources differ on whether a **multigraph** *must* or only *may* contain multiple edges.

Similarly, sources differ on whether a **multigraph** may contain loops, and whether a loop counts as a double edge.

If there is any ambiguity, and especially if it matters to the proof, these conditions should be specified.

## Also see

- Results about
**multigraphs**can be found here.

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.6$: Networks as Mathematical Models