The Geometry Junkyard

Euler's Formula, Proof 19: Integer-Point Enumeration

If we are given some shape S in the plane, let pS(n) denote the number of points with integer coordinates in a copy of S scaled by the positive integer factor n. We can compute a formula for p(n) in many simple cases:

Note that in all these cases p is a polynomial, with degree equal to the dimension of S, and abs(p(0)) = 1.

Now, as in the other proof via Pick's theorem, we draw our planar graph with integer coordinates in the plane. We can calculate the number of integer points covered by scaled copies of our drawing in two ways: one as pS(n) for the closed polygon bounded by the drawing's outer face, and one as the sum of pS(n) over all other vertices, open edges, and interiors of interior faces of the drawing.

That is,

sumv in V pv(n) + sume in E pint(e)(n) + sumf in F pint(f)(n) = pcl(outer face)(n) + pint(outer face)(n).

(The term on the right hand side for the interior of the outer face is included to cancel that face from the sum on the left hand side, since we really wanted to sum only the interior faces of the drawing but the sum as written includes all faces.)

Evaluating these polynomials at n=0 doesn't change this equality:

sumv in V pv(0) + sume in E pint(e)(0) + sumf in F pint(f)(0) = pcl(outer face)(0) + pint(outer face)(0).

But the left hand side of this equality has +1 for each vertex and face of the graph, and -1 for each edge, while the right hand side is 2, so Euler's formula follows.

The Ehrhart-Macdonald Theorem lets us conclude that abs(p(0))=1 for higher-dimensional relatively open convex polytopes, allowing this proof to be generalized to any convex polytope in Rd with integer or rational vertex coordinates (Beck and Robins, Theorem 5.2). All polyhedra in R3 can be realized with integer coordinates but this is not true for all higher dimensional polytopes.

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: .