Graph of polytope and hyperplane Suppose that $P$ is a compact and convex polytope in $R^d$ and let $G$ be the graph of $P$ ($V(G)$ are the vertices of $P$ and $E(G)$ are the $1$-dimensional faces - for example polyedral graphs are the graphs of polytopes in $R^3$ http://en.wikipedia.org/wiki/Polyhedral_graph)
By Balinski's theorem (http://en.wikipedia.org/wiki/Balinski%27s_theorem) we know that those graphs are $d$-vertex-connected (http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29).
But I don't know how to prove something stronger. Suppose that we are given a hyperplane $L$ which splits $P$ into two parts. Let $x$, $y$ be two vertices located in the same part of $P$. I would like to prove that there exists a path in $G$, between $x$ and $y$, such that the path uses only vertices from the same part of $P$.
 A: Say $L^+$ is the closed half-space of $L$ containing $x$ and $y$.
For each vertex $v$ of $P \cap L^+$,
consider $d(v,L)$, the distance from $v$ to $L$.
Since there are finitely many vertices, some vertex or vertices will have the maximum distance
from $L$. If there's more than one vertex with the maximum distance,
then clearly their convex hull $F$ is a face of $P$ (no vertices can lie beyond the hyperplane, parallel to $L$, containing $F$.) Otherwise, let $F$ be the unique vertex with maximum distance from $L$.
If $x$ and $y$ are in $F$, then we are done: a path exists from $x$ to $y$ within $F$.
Otherwise, assume $x \notin F$ and we'll connect $x$ to a vertex of $F$. (Then we're done, since we can connect $y$ to $F$ the same way.)
For all the vertices $w$ adjacent to $x$, some must have $d(w,L) > d(x,L)$.
Otherwise, all the edges incident to $x$ lie in the half-space $\{z : d(z,L) \leq d(x,L)\}$, where we are using the notational convenience that points in $L^-$ have negative distance from $L$. But then all the 2-faces incident to $x$ also lie in that half-space, etc, so that all the faces incident to $x$ lie in that half-space; but $P$ is contained in the cone spanned by $x$ and its incident faces, a contradiction.
So: some edge at $x$ moves further from $L$. Similarly, at every vertex in $P \cap L^+$ but not in $F$, some edge moves further from $L$. Keep choosing these edges and you will construct an edge-path from $x$ into $F$.
Do the same thing for $y$ and we are done.
