If we are given some shape S in the plane, let
p_{S}(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:

- If S is a single integer point, then p
_{S}(n) = 1 - If S is an open line segment with integer endpoints,
containing k integer points, then p
_{S}(n) = (k+1)n - 1. If it's a closed line segment, then p_{S}(n) = (k-1)n + 1. - If S is the interior of a polygon with integer vertices, area A, and k
boundary points, then by Pick's theorem
p
_{S}(n) = An^{2}- (k/2)n + 1. If instead S is the closure of such a polygon, then instead we get p_{S}(n) = An^{2}+ (k/2)n + 1.

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 p_{S}(n) for the closed
polygon bounded by the drawing's outer face, and one as the sum of
p_{S}(n) over all other vertices, open edges, and interiors of
interior faces of the drawing.

That is,

sum_{v in V} p_{v}(n) +
sum_{e in E} p_{int(e)}(n) +
sum_{f in F} p_{int(f)}(n)
=
p_{cl(outer face)}(n) +
p_{int(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:

sum_{v in V} p_{v}(0) +
sum_{e in E} p_{int(e)}(0) +
sum_{f in F} p_{int(f)}(0)
=
p_{cl(outer face)}(0) +
p_{int(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 **R**^{d} with
integer or rational vertex coordinates (Beck
and Robins, Theorem 5.2). All polyhedra in **R**^{3} 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: .