## Task 6 - 190936

For suitable natural numbers $n$, there are polyhedra with $n$ vertices and fewer than $n$ faces. For example, for $n=8$, a cuboid is such a polyhedron, as it has exactly 8 vertices and is bounded by exactly 6 planar faces (rectangles).

Investigate whether there exists a natural number $N$ such that for every natural number $n \geq N$, there is a polyhedron with $n$ vertices that is bounded by fewer than $n$ planar faces!

If this is the case, determine the smallest natural number $N$ with this property!
Let $m \geq 3$ be a natural number. Then the right prism whose base and top face are regular $m$-gons has exactly $n=2m$ vertices and possesses $m+2 < m+m=n$ faces. For even numbers $n \geq 6$, such bodies therefore exist.

If one places a four-sided pyramid with a corresponding base on one of the rectangular side faces of such a prism, the number of vertices of the new body increases to $2m+1$ (the apex of the pyramid has been added) and the number of faces increases to $(m+2)-1+4=m+5$ (one face lies inside the new body as the base of the pyramid and thus disappears, while the pyramid adds 4 new faces), which for $m \geq 5$ is still less than the number of vertices $n=2m+1$. Thus, such bodies also exist for odd $n \geq 11$.

For $n=9$, consider a right triangular frustum. This has 3 points each in the base and top face, a total of 6, and 3 additional faces besides the base and top, making a total of 5. If two congruent such frustums are glued together at their bases, the number of vertices of the new body increases to $6+3=9$ and the number of faces increases to $5-1+3+1=8$. Therefore, such a body also exists for $n=9$.

For $n=7$, consider a regular pentagon $ABCDE$ and the line segment $PQ$ formed by shifting the height from $A$ to the opposite side $CD$ perpendicular to the plane of the pentagon. If the points $C$ and $D$ are connected to $Q$ and $A, B$, and $E$ are connected to $P$, a polyhedron with the 7 vertices $A, B, C, D, E, P$, and $Q$ and the faces $ABCDE, CDQ, BCQP, EDQP, ABP$, and $AEP$ is formed; thus, with 6 faces. Therefore, such a body also exists for $n=7$.

Thus, $N=6$ can be chosen, as for every $n \geq 6$ there exists a corresponding body with $n$ vertices and fewer faces.

However, $N<6$ cannot be chosen, as no such body with $e:=n=5$ vertices exists:

Since at least 3 edges emanate from each of these vertices, the sum of these numbers must be at least 15. Since each edge is counted twice (it connects exactly two vertices), there must be at least $k \geq \frac{15}{2}$, and thus also $k \geq 8$, edges in the body.

Let $f$ be the number of its faces. Then, according to Euler's polyhedron formula, $e-k+f=2$. With $e=5$ and $k \geq 8$, it follows that $f=2-e+f \geq 2-5+8=5$, so there can be no such body with 5 vertices but fewer than 5 faces.

Thus, $N=6$ is indeed the smallest such value.