  Given a $d$-dimensional convex polytope $P$ and nonnegative integer $k$ not
exceeding $d-1$, let $G_k (P)$ denote the simple graph on the node set of
$k$-dimensional faces of $P$ in which two such faces are adjacent if there
exists a $(k+1)$-dimensional face of $P$ which contains them both. The graph
$G_k (P)$ is isomorphic to the dual graph of the $(d-k)$-dimensional skeleton
of the normal fan of $P$. For fixed values of $k$ and $d$, the largest integer
$m$ such that $G_k (P)$ is $m$-vertex-connected for all $d$-dimensional
polytopes $P$ is determined. This result generalizes Balinski's theorem on the
one-dimensional skeleton of a $d$-dimensional convex polytope.

Combinatorics