From ProofWiki
Jump to navigation Jump to search


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

That is, $G = \struct {V, E}$ is a multigraph if $V$ is a set and $E$ is a multiset of doubleton subsets of $V$.


The graph above is a multigraph because of the double edge between $v_2$ and $v_3$ and the triple edge between $v_5$ and $v_6$.

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$.


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

The multiplicity of the above example is $3$.

Also defined as

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.