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
Where there is more than one edge between any pair of vertices, each of those edges is called a multiple edge.
Multipliticy
The multiplicity of a multigraph is the maximum multiplicity of its (multiple) edges.
The multiplicity of the above example is $3$.
Note
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.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 1.6$
