Proof that if convex polyhedron doesn't contain triangles and quadrangles then $3m \le 5n - 10$

30 Views Asked by At

Proof that if convex polyhedron doesn't contain triangles and quadrangles then $3m \le 5n - 10$ where $m$ is number of edges and $n$ number of vertices

I don't know how to start this task but I suspect that there is something similar with planar graphs. If planar graph doesn't contain cycle with length $<r$ then we have $$ rf \le 2m \\ rf = 2r - nr + mr \\ (r-2)m \le r(n-2) $$ so in our case for $r=5$ it will be $$ 3m \le 5n - 10 $$

But I don't know if each convex polyhedron is planar graph. Is that true? I did find anything about that in my lecture.

1

There are 1 best solutions below

0
On BEST ANSWER

Using more traditional letters, let $v,e,f$ denote the number of vertices, the number of edges, and the number of faces, respectively.

The key tool is Euler's formula $$v-e+f=2$$ If we count the edges one face at a time, each edge is counted twice, hence $$2e = 5f_5+6f_6+7f_7 + \cdots$$ where $f_k$ denotes the number of faces with exactly $k$ edges.

But clearly $$f=f_5+f_6+f_7 + \cdots$$ hence $2e \ge 5f$, or equivalently, $f\le \frac{2}{5}e$. \begin{align*} \text{Then}\;\;&v-e+f=2\\[4pt] \implies\;&e=v+f-2\\[4pt] \implies\;&e\le v + {\small{\frac{2}{5}}}e -2\\[4pt] \implies\;&{\small{\frac{3}{5}}}e\le v -2\\[4pt] \implies\;&3e\le 5v-10\\[4pt] \end{align*}