Simplex Graph¶

Transform an undirected graph into a bipartite median graph whose vertices are all cliques, including the empty clique, with adjacency given by adding or deleting exactly one original vertex.

Version: v2 · 2026-09-06 · History
Domain-specific #: 2782
Origin domain: mathematics
Subdomain: graph theory
Aliases: Clique simplex graph

Core Idea¶

For an undirected graph \(G\), its simplex graph \(\kappa(G)\) has one vertex for every clique of \(G\), including the empty clique and all singletons. Two vertices of \(\kappa(G)\) are adjacent exactly when the corresponding cliques differ by adding or deleting one vertex—equivalently, their symmetric difference has cardinality one. This is a graph construction, not a label for the clique complex itself and not the better-known clique graph whose vertices are often maximal cliques. Bandelt and van de Vel used the construction in connecting graph coloring, median algebras, and embeddings into products of dendrons.^[1]

The construction turns clique inclusion into unit-step geometry. Distance between two clique-vertices equals the size of their symmetric difference because the intersection is a clique, so one may delete vertices down to the intersection and add vertices up to the target. For three cliques \(A,B,C\), the majority set \((A\cap B)\cup(B\cap C)\cup(C\cap A)\) is again a clique and is their unique median. Consequently every simplex graph is a median graph and therefore bipartite. Later median-graph literature states the construction directly and connects the chromatic number of \(G\) to isometric embedding of \(\kappa(G)\) in a product of trees.^[2]

The identity is the whole mapping graph → all cliques as vertices → one-vertex symmetric-difference edges. Omitting the empty clique changes the distinguished central vertex and can change connectedness conventions. Using only maximal cliques creates another object. A complete graph \(K_n\) has every subset as a clique, so \(\kappa(K_n)\) is the \(n\)-dimensional hypercube. For a triangle-free graph, cliques have size at most two, so the simplex graph contains no cube of dimension three. Imrich, Klavžar, and Mulder use simplex graphs to relate median-graph recognition and triangle-free graph recognition.^[3] The strict parent is Transformation because the construction rule changes one graph into a second while systematically preserving clique-incidence information.

Structural Signature¶

An undirected input graph \(G\). Loops and directed arcs are outside the standard construction unless separately generalized.
All cliques. Every complete vertex subset is represented, not only maximal cliques.
The empty clique. It is a genuine vertex and acts as a distinguished central basepoint.
Singleton cliques. Original vertices appear as neighbors of the empty clique.
Clique-vertices. Vertices of \(\kappa(G)\) are subsets of \(V(G)\), not the original vertices themselves.
Unit symmetric difference. Adjacency means exactly one original vertex is inserted or removed.
Inclusion orientation. Each edge can be oriented from the smaller clique to the larger one in the clique poset.
Hamming distance. Graph distance equals symmetric-difference size between clique subsets.
Median closure. Coordinatewise majority of three clique subsets is a clique and gives the unique median.
Cubical structure. A clique of size \(k\) induces a \(k\)-cube on all its subsets.

What It Is Not¶

Not the clique graph. Clique graphs commonly use maximal cliques and intersection adjacency.
Not the clique complex. The complex is a simplicial complex; the simplex graph is its inclusion-cover graph for all faces.
Not an arbitrary median graph. Every simplex graph is median, but not every median graph has the required central-vertex structure.
Not a graph simplex in spectral geometry. Similar terminology can refer to Euclidean simplices associated with matrices.
Not the network simplex. That is an optimization algorithm on flows.
Not built only from nonempty cliques. The empty clique is part of the standard identity.

Scope of Application¶

Simplex graphs translate clique structure into metric and median-graph geometry.

Median graph theory. Producing canonical median graphs with an identifiable central vertex.
Graph coloring. Relating colorability of the input to tree-product embeddings of the output.
Clique-complex analysis. Representing face-inclusion cover relations as graph edges.
Cubical geometry. Turning each input clique into an induced hypercube through its subsets.
Recognition complexity. Transferring questions between triangle-free graphs and cube-restricted median graphs.
Named graph families. Recovering hypercubes, gear graphs, and Fibonacci cubes from suitable inputs.

Clarity¶

Define clique to include the empty set and every singleton. Use a separate symbol such as \(\kappa(G)\) for the output graph. State that its vertices are clique subsets of \(V(G)\), and that adjacency requires symmetric difference of exactly one—not at most one, which would also admit equality. Distinguish all cliques from maximal cliques. When identifying an output as a hypercube, specify that the input is complete; when claiming a cube restriction, translate cube dimension back to clique size. Prove the median formula by showing that any two vertices in the majority set coexist in at least one of the three input cliques. Do not conflate the simplex graph with the one-skeleton of the clique complex: the latter recovers the original graph, while the former has one vertex per face. Report whether the graph is finite when counting vertices; an input with many cliques can produce exponential output.

Manages Complexity¶

Clique families are downward closed but can be exponentially large and difficult to view as a single object. The simplex-graph transformation externalizes this family as a graph whose edges record one-element changes. Set symmetric difference becomes path length, inclusion becomes edge orientation, and coordinatewise majority becomes a median operation. Cubes appear automatically from subsets of one clique, allowing clique number to be read as cubical dimension. Conversely, tree-product embeddings reflect color assignments in the input. The construction makes local navigation simple—insert or delete one vertex while remaining a clique—even though global enumeration may still be exponential. It therefore organizes complexity rather than compressing output size. The empty clique gives a common origin and ensures every clique is reachable through its subsets. Explicitly retaining all faces prevents maximal-clique summaries from erasing the median and cubical structure.

Abstract Reasoning¶

Enumerate or characterize every clique of the undirected input graph, including the empty set.
Create one output vertex for each clique and retain the subset as its label.
Join two output vertices exactly when their labels differ by one original vertex.
Use subset inclusion to orient or rank edges by clique cardinality when useful.
Compute paths by deleting to an intersection and adding toward the target clique.
Compute the median of three vertices by taking elements present in at least two labels.
Read induced cubes from the full family of subsets of each input clique.
Translate output properties back to clique number, coloring, or embedding properties of the input.

Knowledge Transfer¶

The strict parent is Transformation: a fully specified mapping takes an undirected graph to another graph, changes vertices into cliques, changes adjacency into unit symmetric difference, and preserves selected incidence information in metric form. The transferable pattern is to lift a family of admissible subsets into a state graph connected by atomic edits. The requirement that admissible subsets are cliques, the majority-closure proof, and the resulting median/cubical identities are graph-theoretic accent.

Examples¶

Canonical¶

For \(G=K_3\), every subset of its three vertices is a clique. The eight clique-subsets become the eight vertices of \(\kappa(G)\), and toggling one original vertex gives the edges of the three-dimensional cube \(Q_3\). The empty clique is one corner; three singleton cliques are its neighbors; the full three-vertex clique is the opposite corner.

Mapped back: complete input graph → every vertex subset admissible → one-bit toggle adjacency → hypercube.

Applied / In Practice¶

Let \(G=C_4\). Its cliques are the empty set, four singletons, and four edges; no triangle is a clique. The simplex graph therefore has nine vertices. Empty-to-singleton and singleton-to-incident-edge adjacencies form an eight-cycle around the central empty-clique vertex, a gear-graph form. The absence of three-vertex cliques prevents any induced three-cube.

Mapped back: triangle-free cycle → cliques of sizes 0, 1, 2 only → central median graph with no 3-cube.

Structural Tensions¶

Faithful face structure vs. exponential size. All cliques preserve the geometry but can be numerous. Diagnostic: Is the construction conceptual, implicit, or explicitly enumerated?
All cliques vs. maximal-clique summary. Maximal cliques are compact but destroy unit-edit closure. Diagnostic: Are nonmaximal and empty cliques present?
Subset inclusion vs. graph adjacency. Comparable faces can differ by many vertices. Diagnostic: Are edges restricted to covers with symmetric difference one?
Median closure vs. arbitrary subset families. Majority works because clique families are downward and pairwise compatible. Diagnostic: Was the majority set proved to be a clique?
Autonomous construction vs. generic Transformation. Many graph operators exist. Diagnostic: Does clique-as-vertex plus one-toggle adjacency determine the output uniquely?

Structural–Framed Character¶

All-clique vertex set, empty clique, unit-toggle adjacency, and median consequence are structural. Choice of enumeration algorithm, visualization, vertex naming, and application is framed. The abstraction is domain-specific because its inputs, admissible subsets, and output geometry belong to graph theory.

Structural Core vs. Domain Accent¶

The portable core is input object → rule-defined state objects → atomic-change adjacency → preserved invariants. The domain accent is undirected graph, clique family, symmetric difference one, median majority, and cubical faces. Removing it leaves Transformation; retaining it yields Simplex Graph.

Transformation is the strict parent because \(\kappa\) is a rule-governed graph-to-graph mapping that restructures original vertices into clique states while preserving clique inclusion as unit-step metric geometry. Representation is related, but the named construction produces a new combinatorial object with derived invariants.

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

Relationships to Other Abstractions¶

Current abstraction Simplex Graph Domain-specific

Parents (1) — more general patterns this builds on

Simplex Graph is a kind of Transformation Prime

Transformation is the strict parent because \(\kappa\) is a rule-governed graph-to-graph mapping that restructures original vertices into clique states while preserving clique inclusion as unit-step metric geometry.

Hierarchy path (1) — routes to 1 parentless root

Simplex Graph → Transformation → Function (Mapping)

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Clique graph — 0.84
Clique (Graph Theory) — 0.83
Pathwidth — 0.83
Graph Sphericity — 0.81
Quotient Graph — 0.81

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

Not to Be Confused With¶

Clique graph. Usually an intersection graph of maximal cliques.
Clique complex. A simplicial complex whose faces are cliques.
Face poset. The partial order of faces, of which the simplex graph records only cover adjacencies.
Median graph. The broader output class containing simplex graphs.
Hypercube graph. The special output when every subset of the input vertices is a clique.
Network simplex. A linear-programming algorithm unrelated to clique-state construction.

References¶

[1] Hans-Jürgen Bandelt and Marcel van de Vel, ‘Embedding Topological Median Algebras in Products of Dendrons,’ Proceedings of the London Mathematical Society s3-58, no. 3 (1989): 439–453, https://doi.org/10.1112/plms/s3-58.3.439. registry ↩

[2] Hans-Jürgen Bandelt and Victor Chepoi, ‘Metric Graph Theory and Geometry: A Survey,’ in Surveys on Discrete and Computational Geometry (American Mathematical Society, 2008), https://www.math.ucdavis.edu/~saito/data/LapEig/bandelt-chepoi-metric-graphs-survey.pdf. registry ↩

[3] Wilfried Imrich, Sandi Klavžar, and Henry Martyn Mulder, ‘Median Graphs and Triangle-Free Graphs,’ SIAM Journal on Discrete Mathematics 12, no. 1 (1999): 111–118, https://doi.org/10.1137/S0895480197323494. registry ↩