## 13.6 Maximal Cubes in Median Graphs of Circular Split Systems

Let *S* be a nonempty collection of splits (bipartitions of [*n*]) also called a *split system*. Graph *G*(S) has as vertices all sets *X* that contain exactly one element of each split from S and have the property that every pair of elements from *X* intersects. Two vertices *U* and *V* of *G*(S) are adjacent if there exist exactly one split *S* ={*A*, *B*} from S such that either *A* ∈ *U* ∩ *V* or *B* ∈ *U* ∩ *V*. Barthélemy [14] introduced a similar construction by extending Buneman's construction of trees [24] (from a set of compatible splits). Graph *G(S)* is always a median graph [14], and it can be easily seen that the isometric embedding into the corresponding hypercube together with the corresponding binary labeling of vertices is already encoded in the definition of vertices of *G(S)*. Moreover, every median graph can be obtained by such a construction (just consider the set of its splits). *G(S)* is also called a *median network* or *Buneman graph* [32, 33, 60]. In [13, 64] the number of vertices of the median graph *G(S)*, where *S* is the split system of all possible splits of set [*n*], is calculated for *n* ≤ 7.

Bandelt and Dress introduced in [9] circular split systems. For *n* ≥ 3, consider an *n*-cycle *C*_{n} and label its vertices with elements from [*n*]. For *n* ≥ 2, the *full circular split system S(n*) on [*n*] is defined as follows. The full circular split systemS(2) consists of only one possible split of the set [2]; in other words, S(2) = {{{1},{2}}}. For *n*