What is the edge set of a multigraph?

Question

An edge set of a graph is a set of doubletons, pairing edges. For example:

has an edge set of $\{\{6,4\},\{4,5\},\{4,3\},\{5,2\},\{5,1\},\{3,2\},\{1,2\}\}$. A set, by definition, cannot have duplicate elements, else it is not a set.

is a multigraph. All graphs have edge sets, yet the edge set of the multigraph would have to contain duplicate sets in its edge set to properly represent its edges, but then it wouldn't have an edge set, because a set cannot possibly have duplicate elements. I suppose its edge set would be $\{\{1,3\},\{1,2\},\{2,4\},\{2,4\},\{2,4\}\}$, but then it wouldn't be a set, having three instances of the same member.

Question

How do I represent the edge set of a multigraph, which have multiple edges along the same vertices?

Answer 1

I believe the term multiset is used to refer to a set that may have duplicate elements. This term makes sense here, especially since it is cohesive with the term multigraph. If you really want to keep the edgeset as a set you could let each element of the egdeset be a pair that consists of the edge itself and the mutliplicity of the edge. So the edgeset of the multigraph you posted would be $$ \{(\{1,2\},1),(\{1,3\},1),(\{2,4\},3)\} $$ If we go with the multiset term, the question then becomes this: should we call it a multiedgeset or an edgemultiset?

Answer 2

There are different ways to do that and it really depends on what you want to do.

A very nice way is to define an undirected multigraph as $G=(V,E,\text{sig}: E\to \mathcal{P}_2(V))$. Here, $V$ is just any set, we call it vertices, $E$ is just any set, let us call them edges and $\text{sig}: E\to \mathcal{P}_2(V)$ is a map that tells us for a given edge $e\in E$, which two vertices $e$ connects.

Why it is superior to the multiset-option?

Alternatively, you can define $E$ as a multiset, i.e. $E \subseteq \mathcal{P}_2(V)$ together with a multiplicity-map $m: E\to \mathcal{N}$.

I prefer the first way with this signature map $\text{sig}$ over the multiset variant, because it matches the intuition of "different" edges better. IMO the multiset-option describes edges with multiplicities but not multiple edges.

Assume you want to express something like "Take two different edges $e_1$ and $e_2$" formally.

For the $\text{sig}$-option you say "Take $e_1,e_2 \in E$ with $e_1 \not = e_2$". But for the multiset-option, it gets difficult because just saying "Take $e_1,e_2 \in E$, $e_1\not=e_2$" is not enough!