non-degenerate vertices adjacent to exactly $n$ vertices

150 Views Asked by At

For $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^{m}$ let $\mathcal{P}$ be a polytop given by

$$ \mathcal{P} = \{x \in \mathbb{R}^{n} \mid Ax \leq b\}. $$

Let $x$ be a vertex of $\mathcal{P}\subseteq \mathbb{R}^{n}$. We say that $x$ is non-degenerate if $|\text{eq}(\{x\})| = n$, otherwise degenerate. Is it true that every non-degenerate vertex is adjacent to exactly $n$ vertices? Further what is the connection between degenerate vertices and redundant inequalities?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, every non-degenerate vertex has $n$ adjacent vertices. Since each edge arises from the equality in $n-1$ inequalities, there are $\binom{n}{n-1}=n$ incident edges corresponding to a non-degenerate vertex.

In general there is no connection between degenerate vertices and redundant inequalities.

An example of a degenerate vertex is the apex of a pyramid, where the base has more than $n$ vertices. The apex is adjacent to all the other vertices.

Redundant inequalities correspond to inequalities which don't add any value to the representation of the polytope. An easy example are the inequalities $x_1\leq 0$ and $x_1\leq 1$. The second one is obviously not necessary and therefore redundant.