The middle layer graph of order is the vertex-transitive graph whose vertex set consists of all bitstrings of length that have exactly or entries equal to 1, with an edge between any two vertices for which the corresponding bitstrings differ in exactly one bit (Mütze 2016). The conjecture (now proved) that the middle layer graph has a Hamilton cycle for every is known as the middle levels conjecture.
The middle layer graph corresponds to the bipartite Kneser graph . It is the sparsest bipartite Kneser graph and so is in some sense is the hardest obstacle in proving Hamiltonicity for this family of graphs (Mütze 2016). Special cases are summarized in the table below.
-middle layer graph | |
1 | cycle graph |
2 | Desargues graph |
3 | Danzer graph |
The middle layer graph is bipartite, connected, and has vertices (Mütze 2016).
The middle layer graph of order is implemented in the Wolfram Language as GraphData["MiddleLayer", n].