# Voronoi average number of vertices $< 6$

My text says "the average number of vertices of the Voronoi cells is less than six". Then it creates the vertex "at infinity", connects the half-infinite edges to this vertex and shows the equation: $$(v + 1) - e + n = 2$$ where v = number of vertices (before creation of the one at infinity), e is the number of edges, and n is the number of point sites. It then shows the inequality: $$2e \geq 3(v + 1)$$

I've probably been staring at this too long, but how to show the average number of vertices of the Voronoi cells is less than six?

-

Let $F_k$ be the number of Voronoi cells with $k$ vertices. By counting edges you get $2e = 3F_3 + 4F_4 + 5F_5 + \cdots$. The average you seek is $$\frac{3F_3 + 4F_4 + 5F_5 + \cdots}{F_3 + F_4 + F_5 + \cdots} = \frac{2e}{n} \le \frac{2(3n-6)}{n}=6-\frac{12}{n} <6$$
Here I've used that $e\le 3n-6$, which follows from $$2(v+n-1) = 2e \ge 3(v+1) \implies v \le 2n-5 \implies e = v+n-1 \le 3n-6$$
Easier: Let $\deg(f)$ be the number of edges of face $f$. Then $\sum_f \deg(f) = 2e \le 6n-12$ by Euler's formula. The pigeonhole principle now implies that at least one face $f$ has $\deg(f) < 6$. – JeffE Mar 5 '12 at 21:29