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

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

2012-09-10T17:42:14Z

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?

it has a face with three edges, OR
it has a face with four edges with at least one vertex of degree 3 on that face, OR
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?

Answer by Gil Kalai for Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

2012-09-10T22:24:56Z

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 http://mathoverflow.net/questions/10039/characterizing-faces-of-3-dimensional-polyhedra-related-to-victor-eberhards-th/24340#24340

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

Answer by Will Sawin for Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph?

2012-10-05T05:45:48Z

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.

One can view this local Euler characteristic as the simplest case of a discrete analogue of curvature.