The basic tool here is Pick's Theorem: in any polygon P drawn so that it's vertices are on points (x,y) where x and y are both integers, the area of P can be expressed as N + B/2 - 1, where N is the number of integer interior points, and B is the number of integer points on the edges and vertices of P. This can be proven in a number of ways, for instance by choosing a horizontal line L passing below the polygon and partitioning the polygon's area into the sum of signed areas of trapezoids from L to each edge. These proofs do not require Euler's formula so there is no danger of circular reasoning.
First draw the planar graph corresponding to the polygon, with straight line segment edges. It is possible to choose a sufficiently small radius r, such that if we move each vertex somewhere within a circle of that radius centered on its original location, the resulting graph will remain planar; scale the graph so that r=1. Then move every vertex to the nearest integer vertex; the result is an equivalent planar graph drawn in the grid.
The outer face of the graph is covered exactly once by the remaining faces, so the sum of the areas of the remaining faces should equal the area of the outer faces. This sum of areas is, by Pick's Theorem, I+X+B/2+S/2-(F-1), where I is the number of points interior to one of the faces, X is the number of points on an interior edge (each of which counts 1/2 in each of two faces), S is the sum (over all vertices) of the number of interior faces the vertex belongs to, and the (F-1) term comes from adding the -1 term in each of F-1 applications of Pick's theorem.
A vertex interior to the graph contributes a term to S equal to its degree, whereas a vertex on the outer face contributes only its degree minus one. Therefore S=2E-K where K is the number of vertices on the outer face. Further, by Pick's Theorem, the area of the outer face is (I+X+V-K)+(B+K)/2-1. Combining the two equations S=2E-K and I+X+B/2+S/2-(F-1)=(I+X+V-K)+(B+K)/2-1 yields the result.
Unfortunately Pick's theorem does not generalize to higher dimensions, so this approach seems unlikely to work for proving higher-dimensional forms of Euler's formula.
Proofs of Euler's Formula.
From the Geometry Junkyard, computational and recreational geometry pointers.
David Eppstein, Theory Group, ICS, UC Irvine.
Semi-automatically filtered from a common source file. Last update: Sunday, 27-Jan-2013 12:07:01 PST.