Skip to content

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.

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.

Partition is the proposed immediate parent. Compression, Projection, Equivalence Relation, Lossy Abstraction, and Cut are related primes.

The prospective queue contains one strict edge to prime:partition. No live DAG mutation is authorized.

Relationships to Other Abstractions

Local relationship map for Quotient GraphParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Quotient GraphDOMAINPrime abstraction: Partition — is a kind ofPartitionPRIME

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

Neighborhood in Abstraction Space

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

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

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, 5th ed. (Springer, 2017), doi:10.1007/978-3-662-53622-3. registry ↩

[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 ↩