# Two adjacent vertices in a polytope uniquely minimize some linear form

In linear programming, if we model the solution as a polytope, every vertex is a solution.

I'm trying to prove the following statement:

If $x$ and $y$ are two solutions with $n-1$ joint constraints, there exists a solution vector $c$ such that, for each $v\in P$ (the polytope of the problem) that is different from $x$ and from $y$, we have $\langle c,x\rangle = \langle c,y\rangle < \langle c,z\rangle$.

Basically, this means that only $x$ and $y$ are the optimal solutions for the problem. But why is it true? And what is the vector $c$ that exists here?

• I can't quite figure out your question, but in any case I suggest asking your TA or professor. – Yuval Filmus Dec 21 '16 at 15:51
• Hint: try getting an intuition from the 2D case. Generalizing to more dimensions is not too difficult once you understand the 2D solution to your problem. – adrianN Dec 21 '16 at 15:54
• @YuvalFilmus When you see text that doesn't make sense but includes one of < and >, it's a good tip is to take a look at the source. Often, it means the asker has included mathematics outside $...$ and the parser has treated random chunks of it as HTML tags and discarded them. – David Richerby Dec 21 '16 at 17:30
• Try generalizing the proof that for any solution $x$ there exists a solution vector $c$ such that $\langle c,x \rangle < \langle c,z \rangle$ for all $z \neq x$ in the polytope. – Yuval Filmus Dec 21 '16 at 19:18
• thanks guys , great intuition . i'm taking this to account . i'll – ChenSho Dec 22 '16 at 12:46