Many algorithms and procedures require graphs with certain properties. These can be basic properties, such as being undirected, or deeper topology properties, such as being connected or acyclic. In some areas, a key problem is to decide whether two graphs are the same if the vertex names are replaced, i.e. to test whether they are isomorphic.
GraphQ — test whether an expression is a graph object
EdgeQ — test whether an expression is an edge in a graph
VertexQ — test whether an expression is a vertex in a graph
IsomorphicGraphQ — test whether two graphs are the same after vertex renaming
FindGraphIsomorphism — find the graph isomorphism as a list of rules