Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T00:46:57Z http://mathoverflow.net/feeds/question/106835 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/106835/does-eulers-formula-imply-bounds-on-the-degree-of-vertices-in-a-3-polytopal-grap Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph? Manifold Destiny 2012-09-10T17:42:14Z 2012-10-14T17:15:14Z <p>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.</p> <p>Does it imply anything further about the exact degree of the vertices of these faces?</p> <p>In particular, is at least one of the following statements always true for such a polyhedron?</p> <ol> <li>it has a face with three edges, OR</li> <li>it has a face with four edges with at least one vertex of degree 3 on that face, OR </li> <li>it has a face with five edges with at least two vertices of degree 3 on that face?</li> </ol> <p>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. </p> <p>Is there any 3-polytope where none of 1, 2, and 3 hold?</p> http://mathoverflow.net/questions/106835/does-eulers-formula-imply-bounds-on-the-degree-of-vertices-in-a-3-polytopal-grap/106850#106850 Answer by Gil Kalai for Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph? Gil Kalai 2012-09-10T22:24:56Z 2012-09-10T22:24:56Z <p>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. </p> <p>You may want to look at the question and answer on Eberhard's theorem <a href="http://mathoverflow.net/questions/10039/characterizing-faces-of-3-dimensional-polyhedra-related-to-victor-eberhards-th/24340#24340" rel="nofollow">http://mathoverflow.net/questions/10039/characterizing-faces-of-3-dimensional-polyhedra-related-to-victor-eberhards-th/24340#24340</a></p> <p>High dimensional analogues of the result I mentioned in the spirit of your question are very interesting. </p> http://mathoverflow.net/questions/106835/does-eulers-formula-imply-bounds-on-the-degree-of-vertices-in-a-3-polytopal-grap/108889#108889 Answer by Will Sawin for Does Euler's formula imply bounds on the degree of vertices in a 3-polytopal graph? Will Sawin 2012-10-05T05:45:48Z 2012-10-14T17:15:14Z <p>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.</p> <p>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.</p> <p>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.</p> <p>One can view this local Euler characteristic as the simplest case of a discrete analogue of curvature.</p>