Quotient graph

In graph theory, a quotient graph Q of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G. In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]_R, [v]_R) | (u, v) ∈ E(G)}. For example, the condensation of a directed graph is the quotient graph where the strongly connected components form the blocks of the partition.

The result of one or more edge contractions in an undirected graph G is a quotient of G, in which the blocks are the connected components of the subgraph of G formed by the contracted edges. However, for quotients more generally, the blocks of the partition giving rise to the quotient do not need to form connected subgraphs.

If G is a covering graph of another graph H, then H is a quotient graph of G. The blocks of the corresponding partition are the inverse images of the vertices of H under the covering map. However, covering maps have an additional requirement that is not true more generally of quotients, that the map be a local isomorphism.