Elementary Graph Predicates

u adj v : GrphVert, GrphVert -> BoolElt

Returns true if the vertices u and v, both belonging to the same graph G, are adjacent, otherwise false.

e adj f : GrphEdge, GrphEdge -> BoolElt

Returns true if the edges e and f, both belonging to the same graph G, share a common vertex, otherwise false.

u notadj v : GrphVert, GrphVert -> BoolElt

Returns true if the vertices u and v, both belonging to the same graph G, are not adjacent, otherwise false.

e notadj f : GrphEdge, GrphEdge -> BoolElt

Returns true if the edges e and f, both belonging to the same graph G, do not share a common vertex, otherwise false.

u in e : GrphVert, GrphEdge -> BoolElt

Returns true if the vertex u is an endpoint of the edge e, where u and e belong to the same graph, otherwise false.

u notin e : GrphVert, GrphEdge -> BoolElt

Returns true if the vertex u is not an endpoint of the edge e, where u and e belong to the same graph, otherwise false.

G eq H : GrphDir, GrphDir -> BoolElt

G eq H : GrphUnd, GrphUnd -> BoolElt

Returns true if the graphs G and H are identical, otherwise false. G and H are identical if and only if:

-

they are structurally identical,

-

they have the same support,

-

they have identical vertex and edge labels.

Thus, as an example, if G and H are structurally identical graphs, and the vertices of G are labelled while the vertices of H are not, then G eq H returns false.

IsSubgraph(G, H) : Grph, Grph -> BoolElt

Returns true if and only if H is a subgraph of G.

IsBipartite(G) : GrphUnd -> BoolElt

Returns true if the graph G is a bipartite graph, otherwise false.

IsComplete(G) : Grph -> BoolElt

Returns true if the graph G, on p vertices, is the complete graph on p vertices, otherwise false.

IsEulerian(G) : Grph -> BoolElt

Returns true if the graph G is an eulerian graph, otherwise false. A eulerian graph is a graph whose vertices have all even degree. An eulerian digraph is a digraph whose vertices have same in and outdegree. That is, if D is a digraph, D is eulerian if and only if OutDegree(v) equals InDegree(v) for all vertices v of D.

IsForest(G) : GrphUnd -> BoolElt

Returns true if the graph G is a forest, i.e. does not possess any cycles, otherwise false.

IsEmpty(G) : Grph -> BoolElt

Returns true if the graph G is an empty graph, otherwise false. A graph is empty if its edge set E is empty.

IsNull(G) : Grph -> BoolElt

Returns true if the graph G is a null graph, otherwise false. A graph is empty if its vertex set V is empty.

IsPath(G) : Grph -> BoolElt

Returns true if the graph G is a path graph, otherwise false.

IsPolygon(G) : Grph -> BoolElt

Returns true if the graph G is a polygon graph, otherwise false.

IsRegular(G) : Grph -> BoolElt

Returns true if the graph G is a regular graph, otherwise false.

IsTree(G) : Grph -> BoolElt

Returns true if the graph G is a tree, otherwise false.