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

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)=A{n}^2+(k/2)n+1$.

Note that in all these cases $p$ is a polynomial, with degree equal to the dimension of $S$, and $|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}_{\mathrm{int}(e)}(n)+\sum _{f\in F}{p}_{\mathrm{int}(f)}(n)=p_{\mathrm{cl}(\text{outer face})}(n)+p_{\mathrm{int}(\text{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}_{\mathrm{int}(e)}(0)+\sum _{f\in F}{p}_{\mathrm{int}(f)}(0)=p_{\mathrm{cl}(\text{outer face})}(0)+p_{\mathrm{int}(\text{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 $|p(0)|=1$ for higher-dimensional relatively open convex polytopes, allowing this proof to be generalized to any convex polytope in ${\mathbb{R}}^d$ with integer or rational vertex coordinates (Beck and Robins, Theorem 5.2). All polyhedra in ${\mathbb{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.