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.

Creating Edges and Vertices

EdgeSet(G): Grph → GrphEdgeSet

Given a graph \(G\), return the edge-set of \(G\).

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.

VertexSet(G): Grph → GrphVertSet

Given a graph \(G\), return the vertex-set of \(G\).