# 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$. ### `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. ### `V ! v: GrphVertSet, . -> GrphVert` Given the vertex-set $V$ of the graph $G$ and an element $v$ of the support of $V$, create the corresponding vertex of $G$. ### `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$. ### `Index(v): GrphVert -> RngIntElt` Given a vertex $v$ of some graph $G$, return the index of $v$ in the (indexed) vertex-set of $G$. ### `E ! { u, v}: GrphEdgeSet, { . } -> GrphEdge` Given the edge-set $E$ of the graph $G$ and objects $u$, $v$ belonging to the support of $G$, which correspond to adjacent vertices, create the edge $uv$ of $G$. ### `E ! [u, v]: GrphEdgeSet, [ . ] -> GrphEdge` Given the edge-set $E$ of the digraph $G$ and objects $u$, $v$ belonging to the support of $G$, which correspond to adjacent vertices, create the edge $uv$ of $G$. ### `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$. ### `Example: Edge Sets (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 > x := E!{ {1,2}, {3,4}}; > x, Type(x); {{ 1, 2 }, { 3, 4 }} 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. ### `# S: GrphVertSet -> RngIntElt` ### `# S: GrphEdgeSet -> RngIntElt` The cardinality of the set $S$. ### `s in S: GrphVert, GrphVertSet -> BoolElt` ### `s in S: GrphEdge, GrphEdgeSet -> BoolElt` Return `true` if the vertex (edge) $s$ lies in the vertex-set (edge-set) $S$, otherwise `false`. ### `s notin S: GrphVert, GrphVertSet -> BoolElt` ### `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`. ### `S subset T: GrphVertSet, GrphVertSet -> BoolElt` ### `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`. ### `S notsubset T: GrphVertSet, GrphVertSet -> BoolElt` ### `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`. ### `S eq T: GrphVertSet, GrphVertSet -> BoolElt` ### `S eq T: GrphEdgeSet, GrphEdgeSet -> BoolElt` Return `true` if the vertex-set (edge-set) $S$ is equal to the vertex-set (edge-set) $T$. ### `s eq t: GrphVert, GrphVert -> BoolElt` ### `s eq t: GrphEdge, GrphEdge -> BoolElt` Returns `true` if the vertex (edge) $s$ is equal to the vertex (edge) $t$. ### `S ne T: GrphVertSet, GrphVertSet -> BoolElt` ### `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$. ### `s ne t: GrphVert, GrphVert -> BoolElt` ### `s ne t: GrphEdge, GrphEdge -> BoolElt` Returns `true` if the vertex (edge) $s$ is not equal to the vertex (edge) $t$. ### `ParentGraph(S): GrphVertSet -> Grph` ### `ParentGraph(S): GrphEdgeSet -> Grph` Return the graph $G$ for which $S$ is the vertex-set (edge-set). ### `ParentGraph(s): GrphVert -> Grph` ### `ParentGraph(s): GrphEdge -> Grph` Return the graph $G$ for which $s$ is a vertex (edge). ### `Random(S): GrphVertSet -> GrphVert` ### `Random(S): GrphEdgeSet -> GrphEdge` Choose a random element from the vertex-set (edge-set) $S$. ### `Representative(S): GrphVertSet -> GrphVert` ### `Rep(S): GrphVertSet -> GrphVert` ### `Representative(S): GrphEdgeSet -> GrphEdge` ### `Rep(S): GrphEdgeSet -> GrphEdge` Choose some element from the vertex-set (edge-set) $S$. ### `for x in S do ... end for;` The vertex-set (edge-set) $S$ may appear as the range in the `for`-statement. ### `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 ### `EndVertices(e): GrphEdge -> { GrphVert}` ### `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. ### `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. ### `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. ### `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$.