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

v2 · 2026-09-06 · History

Domain-specific #

2613

Origin domain

mathematics

Subdomain

graph theory

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.

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. Equitable partitions and quotient matrices connect graph compression to spectral graph theory.

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.

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.

Relationships to Other Abstractions

Current abstraction Quotient Graph Domain-specific

Parents (1) — more general patterns this builds on

• Quotient Graph is a kind of Partition Prime

  Partition is the proposed immediate parent.

Hierarchy path (1) — routes to 1 parentless root

• Quotient Graph → Partition → Set and Membership

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

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

Computed from structural-signature embeddings · 2026-09-08