---
title: "The Vertex–Set and Edge–Set of Multigraphs"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-vertex-edge-set.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-vertex-edge-set.md"
part: "Combinatorics"
chapter: "Multigraphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Multigraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/index-multigraphs.md"}
prev: {"title": "Construction of Multigraphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-constr.md"}
next: {"title": "Vertex and Edge Decorations", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-decorations.md"}
intrinsics:
  - {"name": "EdgeIndices", "signature": "EdgeIndices(u, v): GrphVert, GrphVert -> SeqEnum"}
  - {"name": "Indices", "signature": "Indices(u, v): GrphVert, GrphVert -> SeqEnum"}
  - {"name": "EdgeMultiplicity", "signature": "EdgeMultiplicity(u, v): GrphVert, GrphVert -> RngIntElt"}
  - {"name": "Multiplicity", "signature": "Multiplicity(u, v): GrphVert, GrphVert -> RngIntElt"}
  - {"name": "Edges", "signature": "Edges(u, v): GrphVert, GrphVert -> SeqEnum"}
  - {"name": "IncidentEdges", "signature": "IncidentEdges(u): GrphVert -> SetEnum"}
  - {"name": "!", "signature": "E ! < { u, v }, i >: GrphEdgeSet, < . > -> GrphEdge"}
  - {"name": "!", "signature": "E ! < [ u, v ], i >: GrphEdgeSet, < . > -> GrphEdge"}
  - {"name": ".", "signature": "E.i {E . i}: GrphEdgeSet, RngIntElt -> GrphEdge"}
  - {"name": "EndVertices", "signature": "EndVertices(e): GrphEdge -> { GrphVert, GrphVert }"}
  - {"name": "EndVertices", "signature": "EndVertices(e): GrphEdge -> [ GrphVert, GrphVert ]"}
  - {"name": "InitialVertex", "signature": "InitialVertex(e): GrphEdge -> GrphVert"}
  - {"name": "TerminalVertex", "signature": "TerminalVertex(e): GrphEdge -> GrphVert"}
  - {"name": "Index", "signature": "Index(e): GrphEdge -> RngIntElt"}
  - {"name": "eq", "signature": "s eq t: GrphEdge, GrphEdge -> BoolElt"}
examples:
  - "ex-16c702"
---

<a id="the-vertex-set-and-edge-set-of-multigraphs"></a>
<a id="multig-vertex-edge-set"></a>
<a id="multigraph-sec-vertex-edge-set"></a>
# 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](https://docs.magma-maths.org/v2.30-1/Combinatorics/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$.

<a id="function-edgeindices-grphvert-grphvert"></a>
## `EdgeIndices(u, v): GrphVert, GrphVert -> SeqEnum`

<a id="function-indices-grphvert-grphvert"></a>
## `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$.

<a id="function-edgemultiplicity-grphvert-grphvert"></a>
## `EdgeMultiplicity(u, v): GrphVert, GrphVert -> RngIntElt`

<a id="function-multiplicity-grphvert-grphvert"></a>
## `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$.

<a id="function-edges-grphvert-grphvert"></a>
## `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$.

<a id="function-incidentedges-grphvert"></a>
## `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$.

<a id="operation-op-grphedgeset"></a>
## `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$.

<a id="operation-op-grphedgeset-2"></a>
## `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$.

<a id="operation-multigraph-e-i"></a>
## `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](https://docs.magma-maths.org/v2.30-1/Combinatorics/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.

<a id="function-endvertices-grphedge"></a>
## `EndVertices(e): GrphEdge -> { GrphVert, GrphVert }`

<a id="function-endvertices-grphedge-2"></a>
## `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]$.

<a id="function-initialvertex-grphedge"></a>
## `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.

<a id="function-terminalvertex-grphedge"></a>
## `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.

<a id="function-index-grphedge"></a>
## `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$.

<a id="operation-op-eq-grphedge-grphedge"></a>
## `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$.

<a id="example-ex-16c702"></a>
## `Example: Edges of a Multigraph (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 > ]
```
