$G$ a maximal simple planar graph with $n$ vertices, $m$ edges and $ki$ vertices of degree $i$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$.

245 Views Asked by At

$G$ is maximal simple planar graph with $n$ vertices and $m$ edges. There are $ki$ vertices of degree $i$, for $i = 1, \dots, n-1$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$.

I got the following but not sure if this is a correct way, or the best way:

If a simple graph is maximal planar with $n$ vertices and $m$ edges then

$\quad m = 3n-6$.

$\therefore 2m = 6n-12$

Also $\sum_{v \in V(G)} d(v) = 2m$

Hence I thought that $\sum_{i= 1}^{n-1}ik_i = 6 \sum_{i= 1}^{n-1}k_i -12$

$\therefore \sum_{i= 1}^{n-1}(6-i)k_i = 12$

Could someone please validate this?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $f$ be the number of faces. Clearly, all the faces of a maximal planar graph are triangles. Since you have $f+n=m+2$ (Euler's theorem), then using $m=3n-6$ we get $f=2n-4$. Further, $\sum k_i=n$. Now, we need to count $\sum ik_i$. But this sums the number of faces incident to a vertex. Since all the faces are triangles, every face will be included three times in this sum, hence $\sum ik_i=3f$. After that the result easily follows: $$\sum_{i=1}^{n-1}(6-i)k_i = 6\sum_{i=1}^{n-1} k_i - \sum_{i=1}^{n-1} ik_i = 6n - 3f = 6n - 3(2n-4) = 12.$$