Proving the upper bound of edges in a convex polyhedron

Question

The question is the following:

Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of edges is at most $5(n-2)/3$.

Assuming the convex polyhedron is in fact planar: Let $n = v = \#\{\text{vertices}\}$, $e = \#\{\text{edges}\}$, $f = \#\{\text{faces}\}$.

$v \geq 5f$, so $v/5 \geq f$.

Plugging the above into Euler's formula...

$v - e + f = 2$

$v - e + v/5 \geq 2$

$6v/5 - e \geq 2$

$6v/5 - 2 \geq e$

I'm not sure where the fact that every vertex has degree $3$ would fit in, but this is for sure not the result the question was asking for.

BUT.

I'm leaning towards this solution, because the question never states that the graph is planar, and the numbers seem more plausible. If the convex polyhedron is NOT planar, the only approach i can think of is the following, which I am also unaware how to finish.

The sum of the degrees $= 2 \#\{\text{Edges}\}$. Since every vertex has a degree of $3$, $3V = 2E$. Also noting that $V \geq 5$.

And I'm stuck here.

If anyone could point me in the right direction I would be greatly appreciative. Thanks.

Answer 1

Let $F$ be the number of faces, $E$ be the number of edges, and $V$ be the number of vertices. Since each face has at least $5$ edges, and each edge is shared between $2$ faces, $$ 2E \geq 5F $$ Using this upper bound on $F$ in Euler's characteristic for convex polyhedra $$ F=2+E-V $$ we get $$ \frac{2E}{5} \geq 2+E-V $$ which, if rearranged, gives $$ E \leq \frac{5(V-2)}{3} $$

Answer 2

The accepted solution is correct, however, you can add the following:

• Every vertex has a degree of 3, so 3 edges belong to it.
• Every edge has 2 vertices.

Therefore: $$2 E = 3 V$$ Using the formerly stated inequality: $$ E \leq \frac{5 (\frac{2}{3}E -2) }{3}$$ $$ 9E \leq 10E - 30$$ The final solution would be: $$E \geq 30$$