3
$\begingroup$

What I am wondering is if the Hirsch conjecture has a simple proof (just a few lines) in $3$ dimensions, perhaps by using Steinitz's theorem or Kuratowski's theorem and some kind of induction argument.

For $d=3$, the Hirsch conjecture states that for a $3$-polytope $P$, the diameter $\delta$ of the graph of $P$ is bounded in terms of the number of faces $F$ by the inequality $\delta \le F - 3.$

Note: in higher enough dimensions $d$ the Hirsch conjecture fails, as was recently shown by Francisco Santos (see http://annals.math.princeton.edu/articles/3941), but it is true for small $d$.

1 Answers 1

1

By Steinitz's theorem, the $1$-skeleton of $P$ is a $3$-connected planar graph. By Euler's formula, we have $V-E+F=2.$ Since every vertex has degree at least $3$, we have $3V\le2E.$ Some algebra yields the bound $F-3\ge g(V),$ where $g(V) \equiv \lceil V/2\rceil-1$. By Menger's theorem, for every pair of nonadjacent vertices $u$ and $v$, there exist $3$ vertex-independent paths from $u$ to $v$. By averaging, the shortest has length at most $h(V) \equiv \lfloor(V-2)/3\rfloor+1$. It is slightly tedious to verify that, for every integer $V \ge 4$, the second inequality in $F-3\ge g(V)\ge h(V)$ holds, which proves that $F-3$ bounds the diameter above.