Inner products of neighboring vertices on a convex polytope

Question

Consider $P$ a convex polytope in $\mathbb R^d$, and $x\in P$ a vertex of $P$. Let $N_P(x)$ be the set of "neighboring" points of $x$. A vertex $y\in P, y\neq x$ is a neighbor of $x$ if $(x,y)$ is an edge (1-dimensional face) of $P$. Mathematically, $(x,y)$ is an edge if and only if there exists $c\in\mathbb R^d$, $c\neq 0$, such that $c^\top (y-x)=0$ and $c^\top (z-x)<0$ for all vertices $z$ different from $x,y$.

Question: Now suppose for some non-zero $c\in\mathbb R^d$, $c^\top (y-x) < 0$ for all $y\in N_P(x)$. Prove that $c^\top(z-x)<0$ as well for all other vertices of $P$.

My attempt (partial solution): when the vertex $x$ is not over-specified (i.e., there are exactly $d$ facets intersecting at $x$), it is not difficult to prove that each facet corresponds to an edge, and therefore $c$ must be in the normal cone of $x$. However, I do not know how this argument could be extended to over-specified $x$.

Answer 1

General: Given a vertex $x_0\in P$ the simplex algorithm computes an optimal vertex $x^*$ which fulfills $c^Tx^*=\max_{y\in P}c^Ty$. In each step, the algorithm moves from vertex to vertex via the edges of the polytope. This yields a sequence of vertices $x_0,x_1,...,x^*$ such that

$c^Tx_0\leq c^Tx_1\leq ...\leq c^Tx^*$

holds.

In this case: Assume there exist vertices $y\notin N_P(x)$, such that $c^T(y-x)\geq 0$ is satisfied. Take a vertex $x^*\neq x$ which maximises $c^Ty$ of all vertices. Therefore, by the simplex algorithm we have a sequence of vertices $x,y_1,...,y_k,x^*$ with $c^Tx\leq c^Ty_1\leq ...\leq c^Tx^*$. Since $x^*\notin N_P(x)$, we have $y_1\in N_P(x)$ with $c^Tx\leq c^Ty_1$ which contradicts $c^T(y_1-x)<0$.