This is an extension from Exercise 2.10 (a) of Bertsimas and Tsitsiklis' Introduction to Linear Optimization.
Exercise 2.10 (a) Consider the standard form polyhedron $P=\{x\mid Ax=b,x\ge0\}$. Suppose that the matrix $A$ has dimensions $m\times n$ and that it rows are linearly independent. If $n=m+1$, then $P$ has at most two basic feasible solutions.
I can easily prove that this is true: Since $n=m+1$, then $\dim N(A)=1$, where $N(A)$ is the null space of $A$. Then we can write $N(A)=\text{span}\{d\}$ for some nonzero $d\in\mathbb{R}^n$. If $x,y,z$ are different BFS of $P$, then $x-y=c_1d$ and $y-z=c_2d$, where $c_1,c_2>0$ without loss of generality. But then $$ y=\frac{c_2}{c_1+c_2}x+\frac{c_1}{c_1+c_2}z $$ contradicts the fact that $y$ is an extreme point.
My question is as follows:
Is there an upper bound for the number of BFS of polyhedra with $n-m=2$?
I tried to apply the same trick of the proof above, but it no longer works. In the one-dimensional case, if distinct $x_1,x_2,x_3\in\text{span}\{d\}$, then there always exist $i,j,k$ distinct such that $x_i\in\text{conv}\{x_j,x_k\}$. However, in the two-dimensional case, there exist distinct $x_1,x_2,x_3,x_4\in\text{span}\{d_1,d_2\}$ such that for all combinations $(i,j,k,\ell)$, $x_i\not\in\text{conv}\{x_j,x_k,x_{\ell}\}$ always.
I also tried to compute the numbers of BFS of some polyehdra with $n-m=2$ (with small $m$ and $n$ of course). In the examples I tried, the number of BFS is always no larger $4$.
Is there a way to prove this or disprove this? More generally:
Apart from the trivial upper bound $\binom{m}{n}$, are there other lower and upper bounds on the numbers of vertices for standard form polyhedra for fixed $(m,n)$?