# Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

A corollary of Euler's formula tells us that the edge-vertex graph of every convex 3-polyhedron must have a face with either 3, 4, or 5 edges, using an argument about the average degree of vertices.

Does it imply anything further about the exact degree of the vertices of these faces?

In particular, is at least one of the following statements always true for such a polyhedron?

1. it has a face with three edges, OR
2. it has a face with four edges with at least one vertex of degree 3 on that face, OR
3. it has a face with five edges with at least two vertices of degree 3 on that face?

It's plainly true for simple 3-polytopes, as every vertex is degree 3. I see that it's also easily true for objects like the (rhombic triacontahedron)[http://en.wikipedia.org/wiki/File:Rhombictriacontahedron.svg] that are highly regular and composed of quadrilateral faces.

Is there any 3-polytope where none of 1, 2, and 3 hold?

-
do you assume that all vertices have degree $\ge 3$, and all faces have $\ge 3$ edges? –  Pietro Majer Sep 10 '12 at 18:06
This does not seem right, including your first claim. We can tile the plane with hexagons. –  Will Jagy Sep 10 '12 at 18:28
But if you take any finite subset of hexagons from that tiling, you're left with a graph where there are multiple edges between the outer face and one of the hexagons, which I assume is not allowed. –  Kevin P. Costello Sep 10 '12 at 19:23
This is not of MO level, voting to close. –  Igor Rivin Sep 10 '12 at 20:31
I have rewritten the question to make explicit that this refers to spherical graphs (indeed, 3-polytopal graphs), not simply planar graphs. –  Manifold Destiny Sep 10 '12 at 21:56

It does follow from Euler's theorem that every graph of a 3-polytope has either a triangle face or a vertex of degree 3. To see this note that if every face has 4 or more edges then $4F \le 2E$ (double count pairs (e,f) where e is an edge f is a face and f contains e.) and now look at Euler's theorem: $2V-2E+2F=4$ so $2V-E \ge 4$ and $E \le 2V-4$ and this imples that there is a vertex of degree 3.

You may want to look at the question and answer on Eberhard's theorem Characterizing faces of 3-dimensional polyhedra. (Related to Victor Eberhard's Theorem [1890]:)

High dimensional analogues of the result I mentioned in the spirit of your question are very interesting.

-
For each face, consider a local Euler characteristic, which is $1$ minus half the number of edges plus, for each vertex, $1$ divided by the degree of the vertex.
The sum of the local Euler characteristics of each face is the global Euler characteristic, since each face is counted as exactly $+1$, each edge as $-1$, and each vertex as $+1$, so is positive.
A face with at least $4$ edges where each vertex has degree at least $4$ has local Euler characteristic no more than $1-e/2+e/4=1-e/4 \leq 0$. A face with exactly $5$ edges where all but one vertex has degree at least $4$ has a local euler characteristic of no more that $1-5/2+4/4-1/3=-1/6 \leq 0$. A face with at least $6$ edges has local Euler characteristic no more than $1-e/2+e/3=1-e/6\leq 0$ Thus there must be at least one face not of those two types, which must therefore be of one of the three types you described.