Based on this thread, it appears to still be open whether:
This has been argued to be equivalent to a projection of a convex solid onto a sphere, where the Euler formula gives us V-E+F=2, counting the outside triangle as a face. Triangulation gives us 2E=3F, which we can define to be 6n.All triangulated planar graphs, where the degree of all the vertices is a multiple of 3, have an even number of vertices.
This gives us V-E/3=2 and V-F/2=2. E=3n, F=2n and V=2+n.
Either n is even, or n is odd.
If n is even V is even and nothing interesting happens.
If n is odd, E=3(mod 6) and F=2(mod 4), and we have a counter example disproving the theorem.
Some observations:
The simplest triangulated graph with the degrees of all vertices a multiple three is the tetrahedron. The octahedron and icosahedron are the only other finite graphs with all vertices having the same degree, of 4 and 5 respectively.
What about three lines connecting the poles? This is dual to the triangle, and the vertices have degree three, but the faces are not triangles.
We can rule out n=1 and n=3. For n=1 we have a triangle, with degree two at each vertex.
For n=3 we can select any triangle. These must be degree 3, so we have at least one edge extending from each (bringing the total number of edges to 6). If exactly one edge extends from consecutive corners they must meet, or else our graph would no longer be triangulated. If one edge extends from each corner we must then have the unique solution for n=2. Thus at least one corner must have degree 6 or higher. But now we have 9 edges and no way to close the triangles.
Constructs have been given (Post #422 of the source thread) for all even n=2 except 4, by starting with n=2 and showing that 4 or 6 vertices can be added to any graph. It is also possible to construct a graph with n=4k-2 by drawing a vertex with degree 3k and closing out the graph as quickly as possible. As an example, consider k=3.
Here we start with a degree 9 point. Since our graph is triangulated planar, we must make a wheel. All the vertices are degree three, but the outer polygon is not a triangle. By connecting five alternating vertices along the wheel we close out four skipped over points, but each connected vertex must have an additional sixth edge. The two adjacent points with a free edge must form a triangle at a new vertex. Now adding a twelfth vertex at the end of the six free edges closes the graph, as expected for n=4(3)-2=10.
But CAN n be odd, for some large n with an irregular pattern?


Reply With Quote