# Voronoi Diagram: Exactly 2n-5 vertices

I want to find some characteristics for a set of points $S$ which contains $n$ points and has some Voronoi Diagram $V(S)$. This diagram should have exactly $2n-5$ vertices.

I tried to use the Euler formula for planar graphs which says $v-e+f = 2$:

$\Rightarrow 2n -5 -e + n = 2 \Rightarrow e = 3n-7$ - but what can I now do with the information that $V(S)$ has $3n-7$ vertices?

$$2n-4 - e + n = 2 \quad \Rightarrow \quad e= 3n - 6.$$
A planar graph has $3n-6$ edges if it is a triangulation (this can als be obtained via Euler's formula – just set $3f=2e$). As a consequence the dual graph to your Voronoi diagram (the Delaunay tessellation) is a triangulation. Or phrased differently, every vertex of your Voronoi diagram has degree~3 and there are three rays.
• Thank you for this. I want exactly $3n-6$ edges...the definintion of a triangulation says there are $<= 3n-6$ edges. is this a problem? May 22, 2016 at 7:56
• Its exactly $3n-6$ edges if the outer face is a triangle (which corresponds to the 3 rays in the Voronoi diagram). May 23, 2016 at 6:05