# The Vertex–Set and Edge–Set of Multigraphs

Much of the functionality for simple graphs (see Section [The Vertex–Set and Edge–Set of a Graph](../Graphs/vertex-edge-set.md#graph-sec-vertex-edge)) also applies to multigraphs. We will not repeat here the functions pertaining to the vertex-set and edge-set of a graph, but concentrate instead on the edges. Indeed, there is a difference in the manner in which multigraph edges are created and accessed when compared to simple graph edges.

Since multigraphs may have multiple edges from $u$ to $v$, it is necessary to know how many of these edges there are, and how each can be accessed. More importantly a scheme is required to uniquely identify an edge.

Recall that a multigraph is represented by means of an adjacency list, so any edge from $u$ to $v$ can be identified by its index in this list. If there is more than one edge from $u$ to $v$, then a list of indices will identify each edge from $u$ to $v$. Thus, the index of the edge in the adjacency list will be the means by which this edge can be *uniquely* identified.

This has a bearing on how an edge can be coerced into a multigraph: Successful coercion will require two vertices $u$ and $v$ so that $v$ is a neighbour of $u$, and a valid index $i$ in the multigraph’s adjacency list. That is, the position $i$ in the list is the index of an edge from $u$ to $v$.

## `EdgeIndices(u, v): GrphVert, GrphVert -> SeqEnum`

## `Indices(u, v): GrphVert, GrphVert -> SeqEnum`

Given vertices $u$ and $v$ of a multigraph $G$, returns the indices of the possibly multiple edge from $u$ to $v$.

## `EdgeMultiplicity(u, v): GrphVert, GrphVert -> RngIntElt`

## `Multiplicity(u, v): GrphVert, GrphVert -> RngIntElt`

Given vertices $u$ and $v$ of a multigraph $G$, returns the multiplicity of the possibly multiple edge from $u$ to $v$. Returns 0 if $u$ is not adjacent to $v$.

## `Edges(u, v): GrphVert, GrphVert -> SeqEnum`

Given vertices $u$ and $v$ of a multigraph $G$, returns all the edges from $u$ to $v$ as a sequence of elements of the edge-set of $G$.

## `IncidentEdges(u): GrphVert -> SetEnum`

Given a vertex $u$ of an undirected multigraph $G$, returns all the edges incident to $u$ as a set of elements of the edge-set of $G$. If $G$ is a multidigraph, the function returns all the edges incident to *and* from $u$ as a set of elements of the edge-set of $G$.

## `E ! < { u, v }, i >: GrphEdgeSet, < . > -> GrphEdge`

Given the edge-set $E$ of the undirected multigraph $G$ and objects $u$, $v$ belonging to the support of $G$ corresponding to adjacent vertices, returns the edge from $u$ to $v$ which corresponds to the edge with index $i$ in the adjacency list of $G$. This requires that the edge at $i$ in the adjacency list of $G$ is an edge from $u$ to $v$.

## `E ! < [ u, v ], i >: GrphEdgeSet, < . > -> GrphEdge`

Given the edge-set $E$ of the multidigraph $G$ and objects $u$, $v$ belonging to the support of $G$ corresponding to adjacent vertices, returns the edge from $u$ to $v$ which corresponds to the edge with index $i$ in the adjacency list of $G$. This requires that the edge at $i$ in the adjacency list of $G$ is an edge from $u$ to $v$.

## `E.i {E . i}: GrphEdgeSet, RngIntElt -> GrphEdge`

Let $E$ be the edge-set of $G$. If $G$ is a simple graph (digraph) then this function is as described in Subsection [Creating Edges and Vertices](../Graphs/vertex-edge-set.md#graph-subsec-vertex-edge-create).

If $G$ is a multigraph or multidigraph, then this function returns the edge at index $i$ in the adjacency list of $G$, provided $i$ is a valid index.

## `EndVertices(e): GrphEdge -> { GrphVert, GrphVert }`

## `EndVertices(e): GrphEdge -> [ GrphVert, GrphVert ]`

Given an edge $e$ in an undirected multigraph $G$, returns the end vertices of $e$ as a set of vertices $\{u, v\}$. If $G$ is a multidigraph, returns $e$’s end vertices as a sequence of vertices $[u, v]$.

## `InitialVertex(e): GrphEdge -> GrphVert`

Given an edge $e = \{u, v\}$ or $e = [u, v]$, returns vertex $u$. This is useful in the undirected case since it indicates, where relevant, the direction in which the edge has been traversed.

## `TerminalVertex(e): GrphEdge -> GrphVert`

Given an edge $e = \{u, v\}$ or $e = [u, v]$, returns vertex $v$. This is useful in the undirected case since it indicates, where relevant, the direction in which the edge has been traversed.

## `Index(e): GrphEdge -> RngIntElt`

Given an edge $e$ in a multi(di)graph $G$, returns the index of $e$ in the adjacency list of $G$.

## `s eq t: GrphEdge, GrphEdge -> BoolElt`

Returns `true` if the edge $s$ is equal to the edge $t$. It $s$ and $t$ are edges in a multi(di)graph $G$, returns `true` if and only if $s$ and $t$ have the same index in the adjacency list of $G$.

## `Example: GrphMult Edges (ex-16c702)`

```magma
> G := MultiGraph< 3 | < 1, {2, 3} >, < 1, {2} >, < 2, {2, 3} > >;

```

The graph $G$ has a loop at vertex 2:

```magma
> Edges(G);
{@ < {1, 2}, 1 >, < {1, 2}, 5 >, < {1, 3}, 3 >, < {2, 2}, 7 >, < {2,
3}, 9 > @}
> E := EdgeSet(G);
> E.7;
< {2, 2}, 7 >
> assert InitialVertex(E.7) eq TerminalVertex(E.7);

```

The graph $G$ has a multiple edge from vertex 1 to vertex 2:

```magma
> u := VertexSet(G)!1;
> v := VertexSet(G)!2;
> I := EdgeIndices(u, v);
> I;
[ 5, 1 ]
> assert #I eq Multiplicity(u, v);
>
> E := EdgeSet(G);
> e1 := E!< { 1, 2 }, I[1] >;
> e2 := E!< { 1, 2 }, I[2] >;
> e1, e2;
< {1, 2}, 5 > < {1, 2}, 1 >
> EndVertices(e1);
{ 1, 2 }
> EndVertices(e2);
{ 1, 2 }
> assert Index(e1) eq I[1];
> assert Index(e2) eq I[2];
>
> assert e1 eq E.I[1];
> assert not e2 eq E.I[1];
> assert e2 eq E.I[2];
> assert not e1 eq E.I[2];

```

We have seen that these two edges can be accessed directly:

```magma
> Edges(u, v);
[ < {1, 2}, 5 >, < {1, 2}, 1 > ]

```