---
title: "The Vertex–Set and Edge–Set of a Graph"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/vertex-edge-set.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/vertex-edge-set.md"
part: "Combinatorics"
chapter: "Graphs"
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": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "Graphs with a Sparse Representation", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/sparse-graphs.md"}
next: {"title": "Labelled, Capacitated, and Weighted Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/labels.md"}
intrinsics:
  - {"name": "EdgeSet", "signature": "EdgeSet(G): Grph -> GrphEdgeSet"}
  - {"name": "Edges", "signature": "Edges(G): Grph -> {@ GrphEdge @}"}
  - {"name": "VertexSet", "signature": "VertexSet(G): Grph -> GrphVertSet"}
  - {"name": "Vertices", "signature": "Vertices(G): Grph -> { GrphVert}"}
  - {"name": "!", "signature": "V ! v: GrphVertSet, . -> GrphVert"}
  - {"name": ".", "signature": "V . i: GrphVertSet, RngIntElt -> GrphVert"}
  - {"name": "Index", "signature": "Index(v): GrphVert -> RngIntElt"}
  - {"name": "!", "signature": "E ! { u, v}: GrphEdgeSet, { . } -> GrphEdge"}
  - {"name": "!", "signature": "E ! [u, v]: GrphEdgeSet, [ . ] -> GrphEdge"}
  - {"name": ".", "signature": "E . i: GrphEdgeSet, RngIntElt -> GrphEdge"}
  - {"name": "#", "signature": "# S: GrphVertSet -> RngIntElt"}
  - {"name": "#", "signature": "# S: GrphEdgeSet -> RngIntElt"}
  - {"name": "in", "signature": "s in S: GrphVert, GrphVertSet -> BoolElt"}
  - {"name": "in", "signature": "s in S: GrphEdge, GrphEdgeSet -> BoolElt"}
  - {"name": "notin", "signature": "s notin S: GrphVert, GrphVertSet -> BoolElt"}
  - {"name": "notin", "signature": "s notin S: GrphEdge, GrphEdgeSet -> BoolElt"}
  - {"name": "subset", "signature": "S subset T: GrphVertSet, GrphVertSet -> BoolElt"}
  - {"name": "subset", "signature": "S subset T: GrphEdgeSet, GrphEdgeSet -> BoolElt"}
  - {"name": "notsubset", "signature": "S notsubset T: GrphVertSet, GrphVertSet -> BoolElt"}
  - {"name": "notsubset", "signature": "S notsubset T: GrphEdgeSet, GrphEdgeSet -> BoolElt"}
  - {"name": "eq", "signature": "S eq T: GrphVertSet, GrphVertSet -> BoolElt"}
  - {"name": "eq", "signature": "S eq T: GrphEdgeSet, GrphEdgeSet -> BoolElt"}
  - {"name": "eq", "signature": "s eq t: GrphVert, GrphVert -> BoolElt"}
  - {"name": "eq", "signature": "s eq t: GrphEdge, GrphEdge -> BoolElt"}
  - {"name": "ne", "signature": "S ne T: GrphVertSet, GrphVertSet -> BoolElt"}
  - {"name": "ne", "signature": "S ne T: GrphEdgeSet, GrphEdgeSet -> BoolElt"}
  - {"name": "ne", "signature": "s ne t: GrphVert, GrphVert -> BoolElt"}
  - {"name": "ne", "signature": "s ne t: GrphEdge, GrphEdge -> BoolElt"}
  - {"name": "ParentGraph", "signature": "ParentGraph(S): GrphVertSet -> Grph"}
  - {"name": "ParentGraph", "signature": "ParentGraph(S): GrphEdgeSet -> Grph"}
  - {"name": "ParentGraph", "signature": "ParentGraph(s): GrphVert -> Grph"}
  - {"name": "ParentGraph", "signature": "ParentGraph(s): GrphEdge -> Grph"}
  - {"name": "Random", "signature": "Random(S): GrphVertSet -> GrphVert"}
  - {"name": "Random", "signature": "Random(S): GrphEdgeSet -> GrphEdge"}
  - {"name": "Representative", "signature": "Representative(S): GrphVertSet -> GrphVert"}
  - {"name": "Rep", "signature": "Rep(S): GrphVertSet -> GrphVert"}
  - {"name": "Representative", "signature": "Representative(S): GrphEdgeSet -> GrphEdge"}
  - {"name": "Rep", "signature": "Rep(S): GrphEdgeSet -> GrphEdge"}
  - {"name": "for", "signature": "for x in S do ... end for;"}
  - {"name": "for-random", "signature": "for random x in S do ... end for;"}
  - {"name": "EndVertices", "signature": "EndVertices(e): GrphEdge -> { GrphVert}"}
  - {"name": "EndVertices", "signature": "EndVertices(e): GrphEdge -> [ GrphVert ]"}
  - {"name": "InitialVertex", "signature": "InitialVertex(e): GrphEdge -> GrphVert"}
  - {"name": "TerminalVertex", "signature": "TerminalVertex(e): GrphEdge -> GrphVert"}
  - {"name": "IncidentEdges", "signature": "IncidentEdges(u): GrphVert -> { GrphEdge}"}
examples:
  - "ex-e2c41e"
  - "ex-12cef7"
---

<a id="the-vertex-set-and-edge-set-of-a-graph"></a>
<a id="vertex-edge-set"></a>
<a id="graph-sec-vertex-edge"></a>
# The Vertex–Set and Edge–Set of a Graph

## Introduction

Let $G$ be a graph on $n$ vertices and $m$ edges whose vertex-set is $V = \{v_1, \ldots, v_m\}$ and edge-set is $E = \{e_1, \ldots, e_m\}$. A graph created by Magma consists of three objects: the *vertex-set* $V$, the *edge-set* $E$, and the graph $G$ itself. The vertex-set and edge-set of a graph are *enriched* sets and consequently constitute types. The vertex-set and edge-set are returned as the second and third arguments, respectively, by all functions which create graphs. Alternatively, a pair of functions are provided to extract the vertex-set and edge-set of a graph $G$. The main purpose of having vertex-sets and edge-sets as types is to provide a convenient mechanism for referring to vertices and edges of a graph. Here, the functions applicable to vertex-sets and edge-sets are described.

<a id="creation"></a>
<a id="graph-subsec-vertex-edge-create"></a>
## Creating Edges and Vertices

<a id="function-edgeset-grph"></a>
### `EdgeSet(G): Grph -> GrphEdgeSet`

Given a graph $G$, return the edge-set of $G$.

<a id="function-edges-grph"></a>
### `Edges(G): Grph -> {@ GrphEdge @}`

A set $E$ whose elements are the edges of the graph $G$. Note that this creates an indexed set and not the edge-set of $G$, in contrast to the function `EdgeSet`.

<a id="function-vertexset-grph"></a>
### `VertexSet(G): Grph -> GrphVertSet`

Given a graph $G$, return the vertex-set of $G$.

<a id="function-vertices-grph"></a>
### `Vertices(G): Grph -> { GrphVert}`

A set $V$ whose elements are the vertices of the graph $G$. In contrast to the function `VertexSet`, this function returns the collection of vertices of $G$ in the form of an indexed set.

<a id="operation-op-grphvertset"></a>
### `V ! v: GrphVertSet, . -> GrphVert`

Given the vertex-set $V$ of the graph $G$, coerce $v$ to a vertex of $G$. If $v$ lies in the support of $G$, return the corresponding vertex. If $v$ is an integer $i$ with $1 \leq i \leq \#V$, return the vertex with index $i$ (equivalent to `V . i`).

<a id="operation-operation-grphvertset-rngintelt-grphvert"></a>
### `V . i: GrphVertSet, RngIntElt -> GrphVert`

Given a vertex-set $V$ and an integer $i$ such that $1 \leq i \leq \#V$, create the vertex $v_i$ of $V$.

<a id="function-index-grphvert"></a>
### `Index(v): GrphVert -> RngIntElt`

Given a vertex $v$ of some graph $G$, return the index of $v$ in the (indexed) vertex-set of $G$.

<a id="operation-op-grphedgeset"></a>
### `E ! { u, v}: GrphEdgeSet, { . } -> GrphEdge`

Given the edge-set $E$ of an *undirected* graph $G$, coerce the unordered pair $\{u, v\}$ to the edge of $G$ joining the vertices $V!u$ and $V!v$, where $V$ is the vertex-set of $G$. It is an error to use this form on a directed graph; use `E ! [u, v]` for directed graphs.

<a id="operation-op-grphedgeset-2"></a>
### `E ! [u, v]: GrphEdgeSet, [ . ] -> GrphEdge`

Given the edge-set $E$ of a *directed* graph $G$ (not a network), coerce the ordered pair $[u, v]$ to the directed edge of $G$ from vertex $V!u$ to vertex $V!v$, where $V$ is the vertex-set of $G$. It is an error to use this form on an undirected graph; use `E ! {u, v}` for undirected graphs.

<a id="operation-operation-grphedgeset-rngintelt-grphedge"></a>
### `E . i: GrphEdgeSet, RngIntElt -> GrphEdge`

Given an edge-set $E$ and an integer $i$ such that $1 \leq i \leq \#E$, create the $i$-th edge of $E$.

<a id="example-ex-e2c41e"></a>
### `Example: Vertices and Edges of an Odd Graph (ex-e2c41e)`

The construction of vertices and edges is illustrated using the Odd Graph, $O_{3}$. and then form its standard graph.

```magma
> S := Subsets({1..5}, 2);
> O3, V, E := Graph< S | { {u,v} : u,v in S | IsDisjoint(u, v) } >;
> VertexSet(O3);
Vertex-set of O3
> Vertices(O3);
{@ { 1, 5 }, { 2, 5 }, { 1, 3 }, { 1, 4 }, { 2, 4 }, { 3, 5 },
{ 2, 3 }, { 1, 2 }, { 3, 4 }, { 4, 5 } @}
> EdgeSet(O3);
Edge-set of O3
> Edges(O3);
{@ {{ 1, 5 }, { 2, 4 }}, {{ 1, 5 }, { 2, 3 }}, {{ 1, 5 }, { 3, 4 }},
{{ 2, 5 }, { 1, 3 }}, {{ 2, 5 }, { 1, 4 }}, {{ 2, 5 }, { 3, 4 }},
{{ 1, 3 }, { 2, 4 }}, {{ 1, 3 }, { 4, 5 }}, {{ 1, 4 }, { 3, 5 }},
{{ 1, 4 }, { 2, 3 }}, {{ 2, 4 }, { 3, 5 }}, {{ 3, 5 }, { 1, 2 }},
{{ 2, 3 }, { 4, 5 }}, {{ 1, 2 }, { 3, 4 }}, {{ 1, 2 }, { 4, 5 }} @}
> u := V!{1, 2};
> u, Type(u);
{1, 2} GrphVert
> Index(u);
8
> V ! 8;
{1, 2} GrphVert
> x := E!{ {1,2}, {3,4}};
> x, Type(x);
{{ 1, 2 }, { 3, 4 }} GrphEdge
```

<a id="example-ex-12cef7"></a>
### `Example: Coercing Vertices and Edges of a Digraph (ex-12cef7)`

Directed edge coercion uses sequence notation.

```magma
> D, VD, ED := Digraph< 3 | {[1,2],[2,3],[3,1]} >;
> v := VD ! 2;
> v, Type(v);
2 GrphVert
> e := ED ! [1, 2];
> e, Type(e);
[1, 2] GrphEdge
```

## Operations on Vertex-Sets and Edge-Sets

For each of the following operations, $S$ and $T$ may be interpreted as either the vertex-set or the edge-set of the graph $G$. The variable $s$ may be interpreted as either a vertex or an edge. The edge-set and vertex-set support all the standard set operations.

<a id="operation-operation-grphvertset-rngintelt"></a>
### `# S: GrphVertSet -> RngIntElt`

<a id="operation-operation-grphedgeset-rngintelt"></a>
### `# S: GrphEdgeSet -> RngIntElt`

The cardinality of the set $S$.

<a id="operation-op-in-grphvert-grphvertset"></a>
### `s in S: GrphVert, GrphVertSet -> BoolElt`

<a id="operation-op-in-grphedge-grphedgeset"></a>
### `s in S: GrphEdge, GrphEdgeSet -> BoolElt`

Return `true` if the vertex (edge) $s$ lies in the vertex-set (edge-set) $S$, otherwise `false`.

<a id="operation-op-notin-grphvert-grphvertset"></a>
### `s notin S: GrphVert, GrphVertSet -> BoolElt`

<a id="operation-op-notin-grphedge-grphedgeset"></a>
### `s notin S: GrphEdge, GrphEdgeSet -> BoolElt`

Return `true` if the vertex (edge) $s$ does not lie in the vertex-set (edge-set) $S$, otherwise `false`.

<a id="operation-op-subset-grphvertset-grphvertset"></a>
### `S subset T: GrphVertSet, GrphVertSet -> BoolElt`

<a id="operation-op-subset-grphedgeset-grphedgeset"></a>
### `S subset T: GrphEdgeSet, GrphEdgeSet -> BoolElt`

Return `true` if the vertex-set (edge-set) $S$ is contained in the vertex-set (edge-set) $T$, otherwise `false`.

<a id="operation-operation-notsubset-grphvertset-grphvertset-boolelt"></a>
### `S notsubset T: GrphVertSet, GrphVertSet -> BoolElt`

<a id="operation-operation-notsubset-grphedgeset-grphedgeset-boolelt"></a>
### `S notsubset T: GrphEdgeSet, GrphEdgeSet -> BoolElt`

Return `true` if the vertex-set (edge-set) $S$ is not contained in the vertex-set (edge-set) $T$, otherwise `false`.

<a id="operation-op-eq-grphvertset-grphvertset"></a>
### `S eq T: GrphVertSet, GrphVertSet -> BoolElt`

<a id="operation-op-eq-grphedgeset-grphedgeset"></a>
### `S eq T: GrphEdgeSet, GrphEdgeSet -> BoolElt`

Return `true` if the vertex-set (edge-set) $S$ is equal to the vertex-set (edge-set) $T$.

<a id="operation-op-eq-grphvert-grphvert"></a>
### `s eq t: GrphVert, GrphVert -> BoolElt`

<a id="operation-op-eq-grphedge-grphedge"></a>
### `s eq t: GrphEdge, GrphEdge -> BoolElt`

Returns `true` if the vertex (edge) $s$ is equal to the vertex (edge) $t$.

<a id="operation-op-ne-grphvertset-grphvertset"></a>
### `S ne T: GrphVertSet, GrphVertSet -> BoolElt`

<a id="operation-op-ne-grphedgeset-grphedgeset"></a>
### `S ne T: GrphEdgeSet, GrphEdgeSet -> BoolElt`

Returns `true` if the vertex-set (edge-set) $S$ is not equal to the vertex-set (edge-set) $T$.

<a id="operation-op-ne-grphvert-grphvert"></a>
### `s ne t: GrphVert, GrphVert -> BoolElt`

<a id="operation-op-ne-grphedge-grphedge"></a>
### `s ne t: GrphEdge, GrphEdge -> BoolElt`

Returns `true` if the vertex (edge) $s$ is not equal to the vertex (edge) $t$.

<a id="function-parentgraph-grphvertset"></a>
### `ParentGraph(S): GrphVertSet -> Grph`

<a id="function-parentgraph-grphedgeset"></a>
### `ParentGraph(S): GrphEdgeSet -> Grph`

Return the graph $G$ for which $S$ is the vertex-set (edge-set).

<a id="function-parentgraph-grphvert"></a>
### `ParentGraph(s): GrphVert -> Grph`

<a id="function-parentgraph-grphedge"></a>
### `ParentGraph(s): GrphEdge -> Grph`

Return the graph $G$ for which $s$ is a vertex (edge).

<a id="function-random-grphvertset"></a>
### `Random(S): GrphVertSet -> GrphVert`

<a id="function-random-grphedgeset"></a>
### `Random(S): GrphEdgeSet -> GrphEdge`

Choose a random element from the vertex-set (edge-set) $S$.

<a id="function-representative-grphvertset"></a>
### `Representative(S): GrphVertSet -> GrphVert`

<a id="function-rep-grphvertset"></a>
### `Rep(S): GrphVertSet -> GrphVert`

<a id="function-representative-grphedgeset"></a>
### `Representative(S): GrphEdgeSet -> GrphEdge`

<a id="function-rep-grphedgeset"></a>
### `Rep(S): GrphEdgeSet -> GrphEdge`

Choose some element from the vertex-set (edge-set) $S$.

<a id="literal-literal-for-for-x-in-s-do-end-for"></a>
### `for x in S do ... end for;`

The vertex-set (edge-set) $S$ may appear as the range in the `for`-statement.

<a id="literal-literal-for-random-for-random-x-in-s-do-end-for"></a>
### `for random x in S do ... end for;`

The vertex-set (edge-set) $S$ may appear as the range in the `for random` - statement.

## Operations on Edges and Vertices

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

<a id="function-endvertices-grphedge-2"></a>
### `EndVertices(e): GrphEdge -> [ GrphVert ]`

Given an edge $e$ belonging to the graph $G$, return a set containing the two end-vertices of $e$. If $G$ is a digraph return the two end-vertices in a sequence.

<a id="function-initialvertex-grphedge"></a>
### `InitialVertex(e): GrphEdge -> GrphVert`

Given an undirected or directed edge $e$ from vertex $u$ to vertex $v$, return 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 undirected or directed edge $e$ from vertex $u$ to vertex $v$, return 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-incidentedges-grphvert"></a>
### `IncidentEdges(u): GrphVert -> { GrphEdge}`

Given a vertex $u$ of a graph $G$, return the set of all edges incident with the vertex $u$. If $G$ is directed, then the set consists of all the edges incident into $u$ and from $v$.
