A simple chain cannot visit the same vertex twice. A closed chain is one where the first and last vertex are the same. In a simple chain all the x i are distinct. The chromatic number of a graph is the smallest k for which the graph is k-colorable . In a graph, a circuit is a simple, closed chain .
Several results concerning the existence of hamiltonian circuits refer to the closure of a graph.
In a complete graph, all pairs of vertices are adjacent . They are denoted by K n , where n is the number of vertices. The corresponding concept for digraphs is called a complete symmetric digraph, in which every ordered pair of vertices are joined by an arc. Maximal means that there is no larger connected, induced subgraph containing the vertices of the component. Given a graph G, if two vertices of G are identified and any loops or multiple edges created by this identification removed, the resulting graph is called the condensed graph .