# Simplex graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Simplex_graph
> Markdown URL: https://mediated.wiki/source/Simplex_graph.md
> Source: https://en.wikipedia.org/wiki/Simplex_graph
> Source revision: 1317716493
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Graph representing connectivity between cliques of another graph

A graph G and the corresponding simplex graph κ(*G*). The blue-colored node in κ(*G*) corresponds to the zero-vertex clique in G (the empty set), and the magenta node corresponds to the 3-vertex clique.

In [graph theory](/source/Graph_theory), a branch of [mathematics](/source/Mathematics), the **simplex graph** κ(*G*) of an [undirected graph](/source/Undirected_graph) G is itself a graph, with one [node](/source/Vertex_(graph_theory)) for each [clique](/source/Clique_(graph_theory)) (a set of mutually adjacent vertices) in G. Two nodes of κ(*G*) are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex.

The empty set is included as one of the cliques of G that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a [subdivision](/source/Subdivision_(graph_theory)) of G itself. The simplex graph of a [complete graph](/source/Complete_graph) is a [hypercube graph](/source/Hypercube_graph), and the simplex graph of a [cycle graph](/source/Cycle_graph) of length four or more is a [gear graph](/source/Gear_graph). The simplex graph of the [complement graph](/source/Complement_graph) of a [path graph](/source/Path_graph) is a [Fibonacci cube](/source/Fibonacci_cube).

The complete subgraphs of G can be given the structure of a [median algebra](/source/Median_algebra): the median of three cliques A, B, and C is formed by the vertices that belong to a [majority](/source/Majority_function) of the three cliques.[1] Any two vertices belonging to this median set must both belong to at least one of A, B, or C, and therefore must be linked by an edge, so the median of three cliques is itself a clique. The simplex graph is the [median graph](/source/Median_graph) corresponding to this median algebra structure. When G is the [complement graph](/source/Complement_graph) of a [bipartite graph](/source/Bipartite_graph), the cliques of G can be given a stronger structure as a [distributive lattice](/source/Distributive_lattice),[2] and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself [bipartite](/source/Bipartite_graph).

The simplex graph has one vertex for every simplex in the [clique complex](/source/Clique_complex) *X*(*G*) of G, and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in *X*(*G*)) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in *X*(*G*)) are in one-to-one correspondence between *X*(*G*) and κ(*G*).

Simplex graphs were introduced by [Bandelt & van de Vel (1989)](#CITEREFBandeltvan_de_Vel1989),[3] who observed that a simplex graph has no cubes if and only if the underlying graph is [triangle-free](/source/Triangle-free_graph), and showed that the [chromatic number](/source/Chromatic_number) of the underlying graph equals the minimum number n such that the simplex graph can be isometrically embedded into a [Cartesian product](/source/Cartesian_product_of_graphs) of n trees. As a consequence of the existence of [triangle-free graphs with high chromatic number](/source/Mycielskian), they showed that there exist two-dimensional topological [median algebras](/source/Median_algebra) that cannot be embedded into products of finitely many [real trees](/source/Real_tree). [Imrich, Klavžar & Mulder (1999)](#CITEREFImrichKlavžarMulder1999) also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.

## Notes

1. **[^](#cite_ref-1)** [Barthélemy, Leclerc & Monjardet (1986)](#CITEREFBarthélemyLeclercMonjardet1986), page 200.

1. **[^](#cite_ref-2)** [Propp (1997)](#CITEREFPropp1997).

1. **[^](#cite_ref-3)** [Imrich, Klavžar & Mulder (1999)](#CITEREFImrichKlavžarMulder1999) credit the introduction of simplex graphs to a later paper, also by Bandelt and van de Vel, but this appears to be a mistake.

## References

- Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in [Goodman, J.E.](/source/Jacob_E._Goodman); Pach, J.; Pollack, R. (eds.), *Surveys on Discrete and Computational Geometry: Twenty Years Later*, Contemp. Math., vol. 453, Providence, RI: AMS, pp. 49–86.

- Bandelt, H.-J.; van de Vel, M. (1989), ["Embedding topological median algebras in products of dendrons"](http://plms.oxfordjournals.org/cgi/content/abstract/s3-58/3/439), *Proceedings of the London Mathematical Society*, s3-58 (3): 439–453, [doi](/source/Doi_(identifier)):[10.1112/plms/s3-58.3.439](https://doi.org/10.1112%2Fplms%2Fs3-58.3.439){{[citation](https://en.wikipedia.org/wiki/Template:Citation)}}: CS1 maint: deprecated archival service ([link](https://en.wikipedia.org/wiki/Category:CS1_maint:_deprecated_archival_service)).

- Barthélemy, J.-P.; Leclerc, B.; Monjardet, B. (1986), "On the use of ordered sets in problems of comparison and consensus of classifications", *Journal of Classification*, **3** (2): 187–224, [doi](/source/Doi_(identifier)):[10.1007/BF01894188](https://doi.org/10.1007%2FBF01894188), [S2CID](/source/S2CID_(identifier)) [6092438](https://api.semanticscholar.org/CorpusID:6092438).

- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", *[SIAM Journal on Discrete Mathematics](/source/SIAM_Journal_on_Discrete_Mathematics)*, **12** (1): 111–118, [CiteSeerX](/source/CiteSeerX_(identifier)) [10.1.1.28.5906](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.28.5906), [doi](/source/Doi_(identifier)):[10.1137/S0895480197323494](https://doi.org/10.1137%2FS0895480197323494), [MR](/source/MR_(identifier)) [1666073](https://mathscinet.ams.org/mathscinet-getitem?mr=1666073).

- Propp, James (1997), "Generating random elements of finite distributive lattices", *Electronic Journal of Combinatorics*, **4** (2) R15, [arXiv](/source/ArXiv_(identifier)):[math.CO/9801066](https://arxiv.org/abs/math.CO/9801066), [doi](/source/Doi_(identifier)):[10.37236/1330](https://doi.org/10.37236%2F1330), [S2CID](/source/S2CID_(identifier)) [13313188](https://api.semanticscholar.org/CorpusID:13313188).

---
Adapted from the Wikipedia article [Simplex graph](https://en.wikipedia.org/wiki/Simplex_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Simplex_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.