# Elementary Invariants and Predicates for Multigraphs

Most but not all of the invariants and predicates that apply to simple graphs (see Sections [Elementary Invariants of a Graph](../Graphs/invariant.md#graph-sec-inv) and [Elementary Graph Predicates](../Graphs/Boolean.md#graph-sec-pred)) also apply to multigraphs. We list them below.

Let $G$ and $H$ be two graphs. For clarity, we list here once again the conditions under which $G$ is equal to $H$ and $H$ is a subgraph of $G$.

The graphs $G$ and $H$ are equal if and only if:

- they are of the same type,

- they are structurally identical,

- they have the same support,

- they have identical vertex and edge labels,

- if applicable, the total capacity from $u$ to $v$ in $G$ is equal to the total capacity from $u$ to $v$ in $H$.

Also, $H$ is a subgraph of $G$ if and only if:

- they are of the same type,

- $H$ is a structural subgraph of $G$,

- any vertex `v` in $H$ has the same support as the vertex `VertexSet(G)!v` in $G$,

- any vertex `v` in $H$ has the same label as the vertex `VertexSet(G)!v` in $G$,

- any edge `e` in $H$ has the same label as the edge `EdgeSet(G)!e` in $G$,

- if applicable, the total capacity from $u$ to $v$ in $G$ is at least as large as the total capacity from $u$ to $v$ in $H$.

Note that the truth value of the above two tests is not dependent on the weights of the edges of the graphs, should these edges be weighted.

Finally, we have introduced a few predicates to help users determine if a general graph is simple or not, undirected or not.

## `Order(G): GrphMult -> RngIntElt`

## `NumberOfVertices(G): GrphMult -> RngIntElt`

The number of vertices of the graph $G$.

## `Size(G): GrphMult -> RngIntElt`

## `NumberOfEdges(G): GrphMult -> RngIntElt`

The number of edges of the graph $G$.

## `u adj v: GrphVert, GrphVert -> BoolElt`

Let $u$ and $v$ be two vertices of the same graph $G$. If $G$ is undirected, returns `true` if and only if $u$ and $v$ are adjacent. If $G$ is directed, returns `true` if and only if there is an edge directed from $u$ to $v$.

## `e adj f: GrphEdge, GrphEdge -> BoolElt`

Let $e$ and $f$ be two edges of the same graph $G$. If $G$ is undirected, returns `true` if and only if $e$ and $f$ share a common vertex. If $G$ is directed, returns `true` if and only if the terminal vertex of $e$ ($f$) is the initial vertex of $f$ ($e$).

## `u notadj v: GrphVert, GrphVert -> BoolElt`

The negation of the `adj` predicate applied to vertices.

## `e notadj f: GrphEdge, GrphEdge -> BoolElt`

The negation of the `adj` predicate applied to edges.

## `u in e: GrphVert, GrphEdge -> BoolElt`

Let $u$ be a vertex and $e$ an edge of a graph $G$. Returns `true` if and only if $u$ is an end-vertex of $e$.

## `u notin e: GrphVert, GrphEdge -> BoolElt`

The negation of the `in` predicate applied to a vertex with respect to an edge.

## `G eq H: GrphMultUnd, GrphMultUnd -> BoolElt`

## `G eq H: GrphMultDir, GrphMultDir -> BoolElt`

## `G eq H: GrphNet, GrphNet -> BoolElt`

Returns `true` if and only if the graphs $G$ and $H$ are equal, that is if and only if they are structurally equal and are compatible with respect to their support, vertex and edge labels, and edge capacities (see the introduction to this section).

## `IsSubgraph(G, H): GrphMultUnd, GrphMultUnd -> BoolElt`

## `IsSubgraph(G, H): GrphMultDir, GrphMultDir -> BoolElt`

## `IsSubgraph(G, H): GrphNet, GrphNet -> BoolElt`

Returns `true` if and only if $H$ is a subgraph of $G$, that is, if and only if $H$ is a structural subgraph of $G$ and the graphs are compatible with respect to their support, vertex and edge labels, and edge capacities (see the introduction to this section).

## `IsBipartite(G): GrphMultUnd -> BoolElt`

Returns `true` if and only if the graph $G$ is bipartite.

## `Bipartition(G): GrphMultUnd -> [ { GrphVert} ]`

Given a bipartite graph $G$, return its two partite sets in the form of a pair of subsets of $V(G)$.

## `IsRegular(G): GrphMult -> BoolElt`

Returns `true` if and only if $G$ is a regular graph.

## `IsComplete(G): GrphMult -> BoolElt`

Returns `true` if and only if the graph $G$, on $n$ vertices, is the complete graph on $n$ vertices.

## `IsEmpty(G): GrphMult -> BoolElt`

Returns `true` if and only if the edge-set of the graph is empty.

## `IsNull(G): GrphMult -> BoolElt`

Returns `true` if and only if the vertex-set of the graph is empty.

## `IsSimple(G): GrphMult -> BoolElt`

## `IsSimple(G): Grph -> BoolElt`

Returns `true` if and only if $G$ is a simple graph.

## `IsUndirected(G): GrphMult -> BoolElt`

## `IsUndirected(G): Grph -> BoolElt`

Returns `true` if and only if $G$ is a undirected graph.

## `IsDirected(G): GrphMult -> BoolElt`

## `IsDirected(G): Grph -> BoolElt`

Returns `true` if and only if $G$ is a directed graph.