Prove: For any pair of positive integers $(v,f)$ satisfying $f≤2v−4$ and $v ≤ 2f − 4$ there exists a polyhedron with $v$ vertices and $f$ faces

Question

Finding examples is one thing, but I don't get how to prove it broadly, though I'm fairly certain it should be true.

Answer 1

Yes. As long as $v, f$ satisfy $2v - f \ge 4$ and $2f - v \ge 4$, one can find a polyhedron with $v$ vertices and $f$ faces.

---

Let $n = \min(2v - f, 2f - v) \ge 4$ and $s = |f-v|$.

Consider a $(n-1)$-pyramid, it has $n$ vertices and $n$ faces.

There are $3$ possible cases:

1. $s = 0$, then $v = f = n$ and the $(n-1)$-pyramid is what one need.

2. $f > v$, by repeat replacing a triangular face with a triangular pyramid for $s$ times, one obtain a polyhedron with $n + s = v$ vertices and $n+2s = f$ faces.

   Following is an example for $n = 6, s = 3$ with $f > v$ which has $v = 9$ vertices and $f = 12$ faces.
   

3. $f < v$, by repeat replacing an edge on the base with a rectangle for $s$ times, one will obtain a polyhedron with $n + 2s = v$ vertices and $n + s = f$ faces.

   Following is another example for $n = 6, s = 3$ but with $f < v$. It has $v = 12$ vertices and $f = 9$ faces instead.