When is a complete graph a polyhedral graph?

102 Views Asked by At

A polyhedral graph is the graph build from the vertices and edges of a convex polyhedron (finite intersection of half spaces). For example, the complete graph $K_n$ is the polyhedral graph of the $(n-1)$-dimensional simplex, hence can be realized in $n$ dimensions.

enter image description here

For dimensions $n=1,2,3$ the $K_{n+1}$ is the biggest complete graph that can be realized here. But I read (Optimization, Jarre & Stoer) that in dimension 4 and above this rule breaks down. For example, it is claimed that $K_6$ is a polyhedral graph in four dimensions.

Question: Can you give me an example for a convex polyhedron in four dimensions which realizes $K_6$?

Note that convexity is an important assumption as seen for the Szilassi polyhedron, which is a 3-dimensional realization of $K_7$.

Extra: What is so special about dimension four that this general rule breaks down here. Which $K_n$ can be realized in $m$ dimensions?