Kvant Math Problem 94

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m06s
Source on kvant.digital

Problem

Prove that there does not exist a polyhedron such that at least four edges are incident to each vertex and at least four edges are incident to each face.

L. G. Limanov

Exploration

Let $V$, $E$, and $F$ denote the numbers of vertices, edges, and faces of the polyhedron.

The conditions translate into two combinatorial inequalities. Since at least four edges meet at every vertex, the sum of the vertex degrees is at least $4V$. The sum of all vertex degrees equals $2E$, because every edge contributes $1$ to the degree count of each of its two endpoints. Hence

$$2E\ge 4V,$$

$$E\ge 2V.$$

Similarly, if every face is bounded by at least four edges, then the sum of the numbers of sides of all faces is at least $4F$. Every edge is incident to exactly two faces, so this sum equals $2E$. Thus

$$2E\ge 4F,$$

$$E\ge 2F.$$

Combining these with Euler's formula,

$$V-E+F=2,$$

should lead to a contradiction.

To check whether there is any hidden issue, consider the extremal possibility where every vertex has degree exactly $4$ and every face is a quadrilateral. Then $2E=4V$ and $2E=4F$, so $V=F=E/2$. Euler's formula would give

$$\frac E2-E+\frac E2=0,$$

contradicting $2$. Thus even the most favorable case fails. The crucial point is making sure the counting identities $2E=\sum \deg(v)$ and $2E=\sum$ (numbers of sides of faces) are used correctly.

Problem Understanding

We must prove that no polyhedron exists for which every vertex is incident with at least four edges and every face is incident with at least four edges.

This is a Type B problem, a pure proof.

The core difficulty is converting the geometric conditions into inequalities involving $V$, $E$, and $F$, then showing that these inequalities are incompatible with Euler's formula for polyhedra.

Proof Architecture

The first lemma is that $E\ge 2V$. This follows because the sum of the degrees of all vertices equals $2E$, while every vertex has degree at least $4$.

The second lemma is that $E\ge 2F$. This follows because the sum of the numbers of sides of all faces equals $2E$, while every face has at least four sides.

The third step is to combine these inequalities with Euler's formula $V-E+F=2$.

The hardest point is the second lemma, because one must correctly justify that each edge contributes exactly twice to the total count of face sides.

Solution

Let $V$, $E$, and $F$ be the numbers of vertices, edges, and faces of the polyhedron.

Since at least four edges are incident to every vertex, every vertex has degree at least $4$. Summing the degrees of all vertices gives

$$\sum_{v}\deg(v)\ge 4V.$$

Each edge has two endpoints and contributes $1$ to the degree count of each endpoint. Hence

$$\sum_{v}\deg(v)=2E.$$

Therefore

$$2E\ge 4V,$$

$$E\ge 2V.$$

Next, let $s(f)$ denote the number of edges bounding a face $f$. By hypothesis,

$$s(f)\ge 4$$

for every face. Summing over all faces,

$$\sum_{f}s(f)\ge 4F.$$

Each edge belongs to exactly two faces of a polyhedron, and contributes $1$ to the boundary count of each of those faces. Consequently,

$$\sum_{f}s(f)=2E.$$

Hence

$$2E\ge 4F,$$

$$E\ge 2F.$$

Adding the inequalities $V\le E/2$ and $F\le E/2$ yields

$$V+F\le E.$$

Therefore

$$V-E+F=(V+F)-E\le 0.$$

On the other hand, Euler's formula for a polyhedron states that

$$V-E+F=2.$$

This contradiction shows that no such polyhedron can exist.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the identity

$$\sum_v \deg(v)=2E.$$

Every edge has exactly two endpoints. When the degrees are summed, each edge is counted once at each endpoint and thus contributes exactly $2$. No edge contributes more or less than $2$, so the total is $2E$.

The second delicate step is the identity

$$\sum_f s(f)=2E.$$

For a polyhedron, every edge is incident with exactly two faces. When the numbers of sides of all faces are added, an edge appears once in the boundary of each of those two faces. Thus each edge contributes exactly $2$ to the sum, giving $2E$.

The final step is the deduction from the inequalities. From $E\ge2V$ and $E\ge2F$ we obtain

$$V\le\frac E2,\qquad F\le\frac E2.$$

Adding gives

$$V+F\le E,$$

hence

$$V-E+F\le0.$$

Euler's formula requires this quantity to equal $2$, producing the contradiction.

Alternative Approaches

One may rewrite the argument in terms of averages. The average vertex degree is

$$\frac{2E}{V},$$

and the average number of sides per face is

$$\frac{2E}{F}.$$

The assumptions imply

$$\frac{2E}{V}\ge4,\qquad \frac{2E}{F}\ge4,$$

which again yields $E\ge2V$ and $E\ge2F$. The contradiction with Euler's formula is then obtained exactly as in the main proof.

The direct counting approach is preferable because it avoids introducing averages and makes the source of the inequalities completely transparent. The contradiction emerges immediately from Euler's formula once the two incidence counts are established.