Triangulation formula in planar graph

129 Views Asked by At

enter image description here

What is the formula relating number of vertices $v,$ number of sides $s$ in a simple planar graph obtained by triangulating a polygonal region into $n$ triangles? Tried to find a constant out of $v+s-n$ etc. but no luck.Thanks in advance.

1

There are 1 best solutions below

2
On BEST ANSWER

It is known that

$$ (v+f)=(e+2),\tag{1} $$

Also we know that your polygonal region is divied into $n$ triangles (faces). In $(1)$ $f=n$. Every face is of size $3$ and if you count around the faces you count each edge twice. All faces have $3$ edges around them, so if there are $f$ faces, hence, there are $3f$ edges counted around them, so $2e=3f$. Putting these together with Euler's formula $(1)$ we get $$ \frac{2e}{3}=f=(2 + e - v). $$