Every planar graph with n vertices have at least n/27 non adjacent pairs of vertices of degree $ \leq 8$

Question

I wont lie - this is for homework.

I am struggling with this task for hours now. I know it has something to do with $k \leq 3n - 6$ but I am just unable to find the connection.

Thanks in advance!

Answer 1

Let us prove this by induction on the number of vertices in our graph, $N$. If $N=0$, this is clearly true. Let our claim hold for all $N <n$.

Given a graph $G$ with at $n$ vertices and $m$ edges, we know that $m\leqslant 3n - 6$, as $G$ is planar. This means that there exists at least one vertex $v$ of degree less than $5$. (If all vertices had degree at least 6, we would have at least $\frac{6n}{2} = 3n > 3n-6$ edges in our graph, a contradiction.)

Remove $v$ from the graph, and use our induction hypothesis. We then have $G-v$ has at least $\frac{n-1}{27}$ non-adjacent pairs of vertices of degree $\leqslant 8$. Call this list $\mathcal{P}$. If $\lceil{\frac{n}{27}}\rceil = \lceil\frac{n-1}{27}\rceil$, we are done. Else, $n \geqslant 27$.

Consider all vertices in $G-v-\Gamma (v)$ , where $\Gamma(v)$ represents the neighbourhood of $v$. This set is non-empty as $n \geqslant 27$ and $\text{deg}(v) \leqslant 5$. They cannot all have degrees $\geqslant$ 8. If they did, we would have at least $\frac{8(n-6)}{2} = 4n-24$ edges in our graph, which is strictly greater than $3n-6$ for $n\geqslant 27$.

So, there is at least one vertex $w$ non-adjacent to $v$, such that both $\text{deg}(v)\leqslant 8$ and $\text{deg}(w) \leqslant 8$. We have found a new pair, which we can add on to our list of pairs, $\mathcal{P}$, to complete our induction step.