Quotient Graph

Collapse each block of a vertex partition into one quotient vertex and push original adjacency through the block map, compressing a graph while recording which aggregate vertices remain connected.

Version

v3 · 2026-09-19 · History

Domain-specific #

2613

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Graph Theory → Mathematics

Aliases

Graph quotient, Partition quotient graph, Factor graph by a vertex partition

Core Idea

Given a graph \(G=(V,E)\) and a partition \(\mathcal P\) of its vertices, the quotient graph has one vertex for each block of \(\mathcal P\). Two quotient vertices are adjacent when an edge of \(G\) joins some vertex in one block to some vertex in the other, subject to the declared rules for loops and parallel edges. The canonical block map \(q:V\to\mathcal P\) sends each original vertex to its equivalence class and pushes adjacency into a compressed graph.

The construction preserves aggregate reachability information while deliberately discarding distinctions inside blocks. In categorical language, the exact quotient depends on the chosen category of simple graphs, multigraphs, directed graphs, or graphs with loops.^[1]

Structural Signature

• An input graph with declared directedness and loop/multiplicity conventions.
• A partition or equivalence relation on its vertex set.
• Quotient vertices identified with partition blocks.
• A surjective block map from original to quotient vertices.
• An adjacency-pushforward rule induced by original edges.
• A decision about self-loops from intra-block edges.
• A decision about multiplicity when many edges map to one block pair.
• A graph homomorphism or compatible quotient morphism.
• Information loss inside each collapsed block.
• Preservation questions for connectivity, degree, spectra, paths, or labels.
• Special cases such as vertex identification and edge contraction.
• Directed condensation when strongly connected components form the blocks.
• Optional equitable-partition conditions giving stronger algebraic behavior.

What It Is Not

It is not an induced subgraph, which deletes vertices rather than identifies them; a graph minor, which may also delete vertices and edges; or the planar dual graph. Edge contraction is only a special quotient whose blocks are connected components of the contracted-edge subgraph. A covering graph projects to a quotient under extra local-isomorphism conditions not required in a general quotient.

Scope of Application

Quotient graphs compress networks, contract components, build condensation DAGs, express symmetry or orbit reductions, support graph homomorphism theory, and reduce state spaces. Diestel's treatment of contractions and minors supplies the standard connected-block special case.^[2] Equitable partitions and quotient matrices connect graph compression to spectral graph theory.^[3]

The construction also appears when coarse-graining Markov or transition graphs, aggregating automaton states, and representing communities, provided the induced-edge semantics are declared.

Clarity

Specify the graph category, partition, edge rule, and whether loops and parallel edges are retained, merged, counted, or discarded. Distinguish the simple quotient from a weighted quotient that records edge counts. State which properties are intended to survive; arbitrary partitions do not preserve distances, degrees, planarity, or spectra.

Manages Complexity

The quotient replaces many vertices by fewer blocks and turns all within-block detail into one aggregate state. It is useful when the analysis cares about inter-block interaction rather than internal structure. The block map makes the loss explicit and allows results to be interpreted as coarse statements rather than claims about every original vertex.

Abstract Reasoning

1. Fix the input graph category and its edge semantics.
2. Choose an equivalence relation on vertices.
3. Verify the classes form a partition.
4. Create one quotient vertex per class.
5. Map every original edge to its pair of endpoint classes.
6. Apply the loop and multiplicity convention.
7. Verify the canonical map is the required graph morphism.
8. Measure what structure is preserved or lost.
9. Refine or coarsen the partition if the quotient is too large or too destructive.

Harary's classical graph-theory framework treats identification and contraction as fundamental graph operations.^[4]

Knowledge Transfer

The portable pattern is declare which entities count as equivalent, collapse each equivalence class to one aggregate node, and push relations forward while making the erased within-class distinctions explicit. The proposed immediate parent is Partition.

Examples

Partitioning every vertex into a singleton returns a graph isomorphic to the original. Putting all vertices of a nonempty graph in one block returns one quotient vertex, with a loop only if the graph convention retains intra-block edges. Contracting one edge identifies its endpoints and is a two-vertex-block quotient.

Collapsing every strongly connected component of a directed graph yields its condensation graph, which is always acyclic.

Structural Tensions

• Compression versus structural fidelity.
• Within-block erasure versus between-block visibility.
• Arbitrary partitions versus equitable or congruent partitions.
• Simple adjacency versus multiplicity or weight retention.
• Quotient universality versus category-dependent conventions.

Structural–Framed Character

Equivalence-class collapse is structural. Vertices, edges, adjacency, graph morphisms, loop conventions, and contractions are constitutive. The abstraction is domain-specific.

Structural Core vs. Domain Accent

The structural core is partition entities -> collapse blocks -> push relations forward. The domain accent is graph adjacency and graph-morphism semantics.

Instantiates / Related Primes

This entry is a kind of Partition.

Partition is the broader abstraction this entry instantiates. Compression, Projection, Equivalence Relation, Lossy Abstraction, and Cut are related primes.

Relationships to Other Abstractions

Current abstraction Quotient Graph Domain-specific

Parents (1) — outgoing typed relations

• Quotient Graph is a kind of Partition Prime

  Partition is the broader abstraction this entry instantiates.

Hierarchy path (1) — routes to 1 parentless root

• Quotient Graph → is a kind of Partition → presupposes Set and Membership

Neighborhood in Abstraction Space

Quotient Graph sits in a sparse region of the domain-specific corpus (78^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Disjoint-Set Data Structure — 0.83
• Homogeneous Graph — 0.83
• Graph canonization — 0.83
• Pathwidth — 0.83
• Friendly-index set — 0.82

Computed from structural-signature embeddings · 2026-10-25

Not to Be Confused With

• Induced subgraph.
• Graph minor as a whole.
• Planar dual graph.
• Edge contraction treated as every quotient.
• Covering graph without its local-isomorphism condition.
• Quotient matrix of a partition treated as the quotient graph itself.

References

[1] Pavol Hell and Jaroslav Nešetřil, Graphs and Homomorphisms (Oxford University Press, 2004), doi:10.1093/acprof:oso/9780198528173.001.0001. registry ↩

[2] Reinhard Diestel, Graph Theory, 5^th ed. (Springer, 2017), doi:10.1007/978-3-662-53622-3. registry ↩ Show verification details

[3] Chris Godsil and Gordon Royle, Algebraic Graph Theory (Springer, 2001), doi:10.1007/978-1-4613-0163-9. registry ↩

[4] Frank Harary, Graph Theory (Addison-Wesley, 1969). registry ↩