ボロノイ図とその３つの性質

母点 $P_1$ のボロノイ領域に属する二点 $A,B$ を取ってくる。

また，他の母点の一つを $P_i$ とする。

「$P_i$ よりも $P_1$ に近い点の集合」は半平面をなす（境界は $P_1P_i$ の垂直二等分線）。この半平面に $A,B$ が属しているので，線分 $AB$ 全体もこの半平面に属す。

つまり，線分 $AB$ 上の任意の点は「$P_i$ よりも $P_1$ に近い」を満たす。以上の議論は各 $i$ について成立するので，線分 $AB$ は $P_1$ のボロノイ領域に含まれる。

背理法で証明する。ボロノイ点を $V$，その点に隣接する領域の母点の一つを $P$ とする。 $V$ を中心とし $VP$ を半径とする円の中に別の母点 $Q$ が含まれるとすると，$VP > VQ$ となる。

よって，$V$ のすぐ近くの点は $P$ よりも $Q$ が近くなるため，$V$ に隣接する領域の母点の一つが $P$ であることに矛盾。

ボロノイ図を十分大きな円でカットした平面グラフ $G$ を考える。 $G$ の頂点数を $V$ ，枝数を $E$ ，面の数を $F$ とおくと，オイラーの多面体定理から $V-E+F=2$ である。

円周上の点の個数を $k$ とすると，$V=v+k$ ，$E=e+k$ である。また，一番外側の領域も面数 $F$ にカウントされているので $F=n+1$ である。

以上より，$(v+k)-(e+k)+(n+1)=2$ ，つまり $v-e+n=1$

また，各ボロノイ点には三本以上の枝が接続しているので，$3v\leq 2e$

ただし，ボロノイ辺は一つまたは二つのボロノイ点に接続する（無限遠に伸びるものは一つの点のみと接続）ことを使った。

以上二つの式から $e$ を消去すると $v\leq 2n-2$

$v$ を消去すると，$e\leq 3n-3$ を得る。