How to approach the proof of this formula for triangulations.

Question

I am currently working on an assignment for my discrete mathematics lecture. It is specifically about graphs which are triangulations and have a minimum degree of 3. Triangulation specifically means here, that every area in the graph is bordered by exactly 3 edges.

The formula that is to be proven is the following:

Let $v_i$ be the number of vertices of degree $i$. Show that the following is true:

$3 v_3 + 2 v_4 + v_5 = v_7 + 2 v_8 + 3 v_9 + ... + (X - 6) v_X + 12$

Whereas $X$ is the maximum degree of the graph in question.

Now, I am specifically supposed to use the Euler Formula, that is $|V| - |E| + g = 2$

I can also calculate the number of edges and areas relative to each other, as I know that every area is bordered by 3 edges and every edge is the border between 2 areas. That means that I know that $3|E| = 2g$.

But I don't know how to go on from here. I specifically struggle with the fact, the the formula doesn't just count vertices, but also differentiates them based on their degree. I don't see how to get there from the Euler formula. I would appreciate any tips that could lead me into the right direction!

Thanks for reading!

Edit:

I have just now realized, that the graph is maximally planar, being a triangulation. Now I can use the fact that $|E| = 3|V| - 6$, but I am not sure where that leads me. I feel like the $-6$ in there might be useful to get to the formula from above, but I can't seem to make the connection, if it even is actually there.

Answer 1

You only forgot to use the Handshaking Lemma. By Handshaking Lemma we have $$\sum_{i = 1}^Xiv_i = 2e \ \ \ (I)$$

where $iv_i$ is the degree sum of vertices with degree $i$ and $e$ is the number of edges. As you suggested, since we have a triangulation, we also have $$e = 3n-6$$ where $n$ is the number of vertices. But we can express $n$ as $n = \sum_{i = 1}^Xv_i$. Then putting it on $(I)$, we have

$$2\bigg(3\sum_{i = 1}^Xv_i-6\bigg) = \sum_{i = 1}^Xiv_i \implies 6\sum_{i = 1}^Xv_i-12 =\sum_{i = 1}^Xiv_i $$ Now, if we write summations term by term, we have $$6v_1+6v_2+...+6v_X-12 = v_1+2v_2+3v_3+...+Xv_X$$

Here, notice that since our graph is a triangulation, we don't have any vertices with degree $1$ or $2$, meaning that $v_1 = v_2 = 0$. Then the result follows by manipulating the below equality:

$$6v_3+...+6v_X -12 = 3v_3+...+Xv_X$$

Answer 2

If you take all the terms to one side, you get $$-3v_3-2v_4-v_5+v_7+\cdots+(X-6)v_X+12.$$ This can be expessed as $$\sum_{i=3}^{X}(i-6)v_i+12,$$ i.e. every vertex $v$ counts for $d(v)-6$ in the sum. Now use the fact that the sum of the degrees is twice the number of edges.