nLab multigraph

Idea

In graph theory a multigraph a particular type of graph. A multigraph is a set of vertices and for each unordered pair of distinct vertices a set of edges between these.

The terminology is used in distinction to

1. simple graphs, which are multigraphs with at most one edge between any unordered pair of distinct vertices;

2. pseudographs, which are like multigraphs but admitted to have “loops” in the sense of edges between a vertex and itself.

Beware that the terminology is not completely consistent across different authors. Some authors may allows loops when they speak of multigraphs.

Definition

More formally this means that a multigraph is

1. a set $V$ (“of vertices”);

2. a set $E$ (“of edges”);

3. a function $E \to \left\{ {\,\atop \,} \{v_1, v_2\} = \{v_2, v_1\} \;\vert\; v_1, v_2 \in V \,,\; v_1 \neq v_2 {\, \atop \,} \right\}$ (sending any edge to the unordered pair of distinct vertices that it goes between).

Specifically a finite multigraph is, after choosing a linear order on its set of vertices, the same as

1. a natural number $v \in \mathbb{N}$ (the number of vertices);

2. for each $i \lt j \in \{1, \cdots, v\}$ a natural number $e_{i,j} \in \mathbb{N}$ (the number of edges between the $i$th and the $j$th vertex)

Examples

• In perturbative quantum field theory the graphs underlying Feynman diagrams are finite multigraphs (e.g. Borinsky).

References

Discussion with an eye towards Feynman diagrams includes

• Michael Borinsky, section 2.1.1 of Algorithmization of the Hopf algebra of Feynman graphs (pdf)

See also

• Wikipedia, Multigraph