Simplex graph

In graph theory, a branch of mathematics, the simplex graph κ(G) of an undirected graph G is itself a graph, with one node for each clique (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 complete subgraphs of G can be given the structure of a median algebra: the median of three cliques A, B, and C is formed by the vertices that belong to a majority 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.

Simplex graphs were introduced by Bandelt & van de Vel (1989),[3] who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free, and showed that the chromatic number of the underlying graph equals the minimum number n such that the simplex graph can be isometrically embedded into a Cartesian product of n trees.

As a consequence of the existence of triangle-free graphs with high chromatic number, they showed that there exist two-dimensional topological median algebras that cannot be embedded into products of finitely many real trees.