Sum of squares of degrees in a planar graph

Question

I'm working through the exercises in Bollobás's book on Modern Graph Theory and am stuck on question (1.67):

Let G be a planar graph on n vertices.

(1) Show that if the minimum degree of G is $\geqslant$ 4, then: $\sum \limits_{v \in V} (deg(v)^2) < 2(n+3)^2 - 62$

(2) Prove by induction on n, that if n $\geqslant$ 4 then: $\sum \limits_{v \in V} (deg(v)^2) \leqslant 2(n+3)^2 - 62$

For the first one I've tried using the fact that if $m$ is the number of edges of G, then for planar graphs $m \leqslant 3n - 6$ so $\sum \limits_{v \in V} deg(v) \leqslant 6n - 12$. Further I think that: $\sum \limits_{v \in V} (deg(v)^2) \leqslant (\sum \limits_{v \in V} deg(v))^2 - 16n(n-1)$

Putting the two results together however didn't yield the required result, so I'm not sure where I have gone wrong.

For the second one, I can't work out what vertex to remove so that induction can be used.

Any help would be much appreciated!

Answer 1

The following are some hints but there is still much to work out, especially for (2). Hopefeully they will not be too confusing:

1. The first part of the exercise is probably more about algebraic inequalities rather than graph theory. We want to maximize $\sum(deg(v)^2)$ knowing that $4\leq deg(v)\leq n-1$ for all $v$ and, as you stated, $\sum deg(v)\leq6n-12$. Should we make the degrees as equal as possible or maybe something else?

2. If the minimum degree is $\geq4$ then we are done by point (1), so suppose not. Now it seems natural to try induction by removing a vertex of minimum degree, say $v_0$. Then $deg(v_0)\in\{0,1,2,3\}$ by assumption. When we add $v_0$ back the sum $\sum(deg(v)^2)$ clearly increases: we have an extra term given by $deg(v_0)^2$ and most importantly the degree of each neighbor of $v_0$ increases by one. The tricky part is bounding the latter increment.

Answer 2

$1.$ Suppose to the converse that there exists a vertex $v$ adjacent to each other vertex of $G$. Then a graph $G$ with the removed vertex $v$ is outerplanar and thus it has a vertex of degree at most two, a contradiction.

Since $\sum_{v\in V}\deg v\le 6n-12$, and $4\le \deg v\le n-2$ for each, by the standard disbalancing argument (if there exist $4<\deg v\le\deg u<n-2$ then when we replace $\deg v$ by $\deg v -1$ and $\deg u$ by $\deg u+1$, the sum $\sum_{v\in V}(\deg v)^2$ will increase), we can show that the maximum

$$2(n-2)^2+(n-2)\cdot 4^2=2n^2+8n-24<2n^2+12n-44=2(n+3)^2-62$$ $$\mbox{ (the inequality is strict since if $n=5$ then $G=K_5$ which is non-planar)}$$

of $\sum_{v\in V}(\deg v)^2$ is attained when two degrees are $n-2$ and the remaining degrees are $4$. This is a case of a double wheel graph, which is a cycle consisting of $n-2$ vertices with two added vertices, inside and outside the cycle, adjacent to each vertex of the cycle.

$1 \Rightarrow 2$. For $n=4$, the claim holds because $$\sum_{v\in V}(\deg v)^2\le 4\cdot 3^2=36=2(n+3)^2-62.$$ Suppose that the claim is proved for $n$. Let $G$ be a planar graph on $n+1$ vertices. If each vertex of $G$ has degree at least four then the induction step follows from (1). Otherwise $G$ contains a vertex $u$ of degree $d\le 3$. Let $N(u)$ be the set of neighbors of $u$ and $V’=V\setminus \{u\}\cup N(u)$. The induction hypothesis implies that

$$S’=\sum_{v\in V’} (\deg v)^2+\sum_{v\in N(u)} (\deg v-1)^2\le 2(n+3)^2-62.$$

Since $$\sum_{v\in V} (\deg v)^2=S’+\sum_{v\in N(u)} (\deg v)^2- (\deg v-1)^2+(\deg u)^2=$$ $$S’+2\sum_{v\in N(u)}\deg v-\deg u+(\deg u)^2,$$ and $\deg u\le 3$, to make the inductive step it suffices to show that

$$2\sum_{v\in N(u)}\deg v+6\le (2(n+4)^2-62)- (2(n+3)^2-62)=4n+14,$$

that is that $\sum_{v\in N(u)}\deg v\le 2n+4$. This is trivial if $|N(u)|\le 2$. Let $|N(u)|=3$. Since $G$ is planar, it is $K_{3,3}$-free, so at most one vertex of $V’$ is adjacent to all vertices of $N(u)$. Since each vertex $v\in N(u)$ has at least $\deg v-3$ neighbors in $V’$, $\sum_{v\in N(u)}(\deg v-3)\le 2|V’|+1=2n-7$, so $\sum_{v\in N(u)}\deg v\le 2n+2$.