TOPICS

# Middle Layer Graph

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].

Bipartite Kneser Graph, Danzer Graph, Desargues Graph, Middle Levels Conjecture, Nonhamiltonian Vertex-Transitive Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Knuth, D. Exercise 56, §7.2.1.3 in The Art of Computer Programming, Vol. 4A. Reading, MA: Addison-Wesley, 2011.Mütze, T. "Proof of the Middle Levels Conjecture." Proc. Lond. Math. Soc. 112, 677-713, 2016.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.

## Cite this as:

Weisstein, Eric W. "Middle Layer Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MiddleLayerGraph.html