Finding all vertices of a polyhedron in $\Bbb{R}^n$ defined by $x_i+x_j\geq1$ and $0\leq x_i\leq 1$ Assume that we have a polyhedron in $\mathbb{R}^n$ defined by the following inequalities:
$$
\begin{cases}
    x_i + x_j \geq 1, \forall i, j \in [1 ,n] : i \neq j \\
    0 \leq x_i \leq 1, \forall i \in [1 ,n]
\end{cases}
$$
For example for $n = 2$ the vertices are $(0, 1), (1, 0), (1, 1)$
How can I find all vertices for an arbitary $n$ ?
 A: A point $P$ is a vertex of a convex polyhedron if and only if:
(1) this point $P$ is in on the polyhedron (by "on" I mean inside or on the surface)
(2) for any non-zero vector $v$, at most one of $P+v,P-v$ is on the polyhedron.
We claim that all the vertices of the polyhedron are of one of the two kinds:
(a) At most one of the coordinates is $0$ and the others are all $1$.
(b) At least three of the coordinates are $1/2$ and the others are all $1$.
Clearly it is trivial that (a) and (b) are on the polyhedral, and (a) are the vertices. For (b), suppose we have point $P(1/2,1/2,\dots,1/2,1,1,\dots,1)$ that is not a vertex, (WLOG first $k\ge 3$ are $1/2$ and the rest are $1$) and vector $v=(a_1,\dots,a_n)$. If one of $a_{k+1},\dots,a_n$ is nonzero (say, $a_n$), we can choose one of $+v$ or $-v$ such that $a_n>0$, and $P$ add that vector is out of the region. Now we have $a_{k+1}=\dots=a_n=0$ and $a_1,a_2\dots,a_k$ are not all zero. Since $k\ge 3$, we can choose two of them, say $a_1,a_2$, that add up not zero (or, if any two if then add up to zero, we have all of them are zero since $k\ge 3$). WLOG we have $a_1+a_2>0$, so $P-v$ has first coordinate sum up less than $1$, it is not in the polyhedral. Contradiction.
Now we consider any point $P(x_1,x_2,\dots,x_n)$ not as (a), (b) above. WLOG $x_1\le x_2\le\dots\le x_n$ and we can clearly have $x_2,\dots,x_n\ge 1-x_1$ and $x_2,\dots,x_n\ge 1/2$. Let $k$ be the laegest index such that $x_k<1$. We have three cases:
(1) $x_1>1/2$.  We have that $x_1<1$ or it is all one and falls into category (a). Let $v=(\varepsilon,0,\dots,0)$ where $\varepsilon=\min(x_1-1/2,1-x_1)$. Clearly $P+v,P-v$ are both on the polyhedron, so $P$ is not the vertex.
(2) $x_1<1/2$. We have that $x_1>0$ or other coordinates are all one and falls into category (a). Let $l$ be the smallest index that $x_l>1-x_1$. It is okay if $l=2$. If $l$ does not exist, that is, $x_2=\dots=x_n=1-x_1$, we define $l=n+1$ and $x_l=1$. Now, choose $\varepsilon=\min(x_1,1/2-x_1,x_{l}-x_{l-1},x_l-1/2)$ and we have $v=(\varepsilon,-\varepsilon,\dots,\varepsilon,0,\dots,0)$ where there are $l-2$ number of consecutive $-\varepsilon$'s. We also have clearly $P+v,P-v$ on the polyhedral.
(3) $x_1=1/2$. We have $x_2,x_3,\dots,x_n\ge 1/2$. Let $u$ be the smallest index that $x_u<1/2$. If $u$ exists, or all coordinates are $1/2$ and falls into (b). Furthermore, if $1/2<x_u<1$, let $v=(0,\dots,0,\varepsilon,0,\dots,0)$ where $\varepsilon=\min(x_u-1/2,1-x_u)$ and it is on the $u$th ccordinate. Clearly $P+v,P-v$ are both on the polyhedron, so $P$ is not the vertex. If $x_u=1$, we have $u=2$ or $u=3$ otherwise it falls into (b) too. For $u=2$, we have $P(1/2,1,1,\dots,1)$ and we can choose $v=(1/3,0,0,\dots,0)$. For $u=3$, we have $P(1/2,1/2,1,\dots,1)$ and we can choose $v=(1/3,-1/3,0,\dots,0)$.
So, in all the ways, $P$ is not the vertex.
Therefore, all vertices are of form (a) and (b).

Here is a 3D representation of the polyhedron inside the hypercube $\{0,1\}^n$ in the case $n=4$ ; one easily recognize vertices $(1,1,1,1)$ on the left and $(1/2,1/2,1/2,1/2)$ in the center.

