Vertex degrees in planar graphs

Question

I am trying to prove the following statement:

Let $G$ be a planar graph and $a, b, c \in V$ three vertices of G. Prove that $d(a) + d(b) + d(c) \le 2|V| + 2$

How should I approach this question as I am not sure why I am given the three vertices? Thank you.

Answer 1

Let $U = V(G) \setminus \{a,b,c\}$. Then at most 2 vertices of $U$ can be adjacent to all 3 vertices of $\{a,b,c\}$ lest $G$ has $K_{3,3}$ as a subgraph. That is the hint right there.

---

So letting $d_U(a)$ be the number of vertices in $U$ that $a$ is adjacent to, $d_U(b)$ be be the number of vertices in $U$ that $b$ is adjacent to, and $d_U(c)$ be be the number of vertices in $U$ that $c$ is adjacent to, it follows that

$$d_U(a) + d_U(b) + d_U(c) \leq 2|U| + 2$$

(Make sure you see why.) However, $|U| = |V|-3$, and $d_U(a) \geq d(a)-2$, $d_U(b) \geq d(b)-2$, $d_U(c) \geq d(C)-2$ (make sure you see why). So the above becomes

$$d(a) + d(b) + d(c) - 6 \le d_U(a) + d_U(b) + d_U(c) \leq 2|U|+2 = 2|V|-4$$

(Make sure you see why). Adding 6 to the above gives you the desired result.

Answer 2

We can prove the statement by induction on the number of vertices. You can easily check the statement holds for the base case which is $|V|=3$. Similarly it is not hard to see the inequality holds for $|V|=4,5$. So let's assume $|V|\geq 6.$ For any given $x,y,z \in V$, we can find $a,b,c \in V$ different than $x,y,z$. By using the hint given by Mike, at least one of the $a,b,c$ cannot be adjacent to all $x,y,z$. Let say it is $c$. Now consider the induced graph $H=G[V-\{c\}]$. Then we have the following from the induction hypothesis $$ d_H(x)+d_H(y)+d_H(z) \leq 2 |H| + 2. $$

Since at most 2 of $x,y,z$ can be connected to $c$, we have $$ d(x)+d(y)+d(z)-2 \leq d_H(x)+d_H(y)+d_H(z). $$

Combining these two inequalities we obtain the desired result.