# A conjecture on planar graphs

I don't know the following is a known result, but it would be very useful to me in my research if it were true.

Conjecture: Let $$G$$ be a planar graph. The sum $$\sum_{\{x,y\} \in E(G)}{\min(\deg(x),\deg(y))}$$ is at most linear in the number of vertices.

• This conjecture would be false if one replaces the minimum by the average - the star graph is a counterexample, in which the sum is quadratic.
• I can prove an upper bound of $$O(n \log(n))$$ as follows. Let $$A_i = \{v : 2^i \leq \deg(v) < 2^{i+1}\}$$, and let $$E_i = \{\{x,y\} \in E(G): x \in A_i ,y \in \cup_{j \geq i}{A_j}\}.$$ Now, $$E(G)$$ is the union of the $$E_i$$'s, and the contribution of an edge from $$E_i$$ is at most $$2^{i+1}$$. On the other hand, as $$G$$ is planar the size of $$E_i$$ is at most $$3|\cup_{j \geq i} A_i |$$. Now, as the average degree in a planar graph is at most 6, the number of vertices whose degree is at least $$2^i$$ is at most $$6n/2^i$$. Therefore $$|E_i| \leq 18 n/ 2^i$$. We have $$\sum_{\{x,y\} \in E(G)}{\min(\deg(x),\deg(y))} \leq \sum_{i=0}^{\log_2(n)} \sum_{\{x,y\} \in E_i}{\min(\deg(x),\deg(y))}$$ $$\leq\sum_{i=0}^{\log_2(n)} |E_i| \cdot 2^{i+1} \leq \sum_{i=0}^{\log_2(n)} (18 n/ 2^i) \cdot 2^{i+1} = 36 n \log_2(n).$$
• Just in the unlikely case that you are not aware of it and that in your work you need to know more about degree-distributions of planar graphs: it might be useful to have a look at the recent work of Drmota, Gimenez, and Noy. For example: arXiv:0911.4331v1 Commented Jul 4, 2017 at 18:26
• Conjecture (modulo details that I do not have time to write out): if $\mathrm{L}(G)$ denotes your function, and if $\mathcal{P}_n:= \text{set of all labelled planar graphs with n vertices}$, then $\frac{1}{\lvert\mathcal{P}_n\rvert}\sum_{G\in\mathcal{P}_n}\frac{\mathrm{L}(G)}{\lvert E(G)\rvert} \sim_{n\to\infty} 4.42652 + o(1)$. Commented Jul 4, 2017 at 19:32
• Just to summarize a bit, and to draw attention to the interesting concept of averages of higher order: it seems that the average of the average of your function (the number defined above) can more or less routinely be calculated to a precision you perhaps did not expect. For example, it seems that said second-order-average can be expressed "in terms" of elementary functions, and hence numerical approximation can be calculated to very many digits of accuracy. (But: something more complicated than "elementary functions" in the contemporary technical sense is involved.) Commented Jul 8, 2017 at 13:36
• The "something more complicated" is the unique real solution of an equation $f(x)=0$ where $f$ in the relevant interval is a strictly monotone increasing Elementary function in the technical sense. This is perhaps getting too terminological, but: evaluating the average of the average of your function involves something like a function elementary relative to a non-algebraic equation. Commented Jul 8, 2017 at 13:44

Let $$L(G)=\sum_{xy\in E(G)} \min\lbrace\deg(x),\deg(y)\rbrace$$.

THM. For a simple planar graph with $$n$$ vertices, $$L(G)\le 18n-36$$ for $$n\ge 3$$.

PROOF. Recall that a simple planar graph with $$k\ge 3$$ vertices cannot have more than $$3k-6$$ edges, achieved by a triangulation. Let the degrees of the vertices be $$d_1\ge d_2\ge\dots\ge d_n$$. We want to choose $$3n-6$$ pairs $$(v_i,w_i)$$ for $$v_i\lt w_i$$ and we want to maximize $$\sum_i d_{w_i}$$. This is achieved by pushing the pairs to the left as much as possible, but we have the constraint that for $$k\ge 3$$ the number of pairs lying in $$\lbrace 1,\ldots,k\rbrace$$ is at most $$3k-6$$. So the best we can hope for is to chose the pairs $$(1,2)$$, $$(1,3)$$ and $$(2,3)$$, then for $$j\ge 4$$ chose 3 pairs $$(x,j)$$ for $$x\lt j$$. This gives $$L(G) \le d_2 + 2d_3 + 3(d_4+\cdots+d_n) \le 3\sum_i d_i \le 3(6n-12).$$

The actual maximums from $$n=3$$ to $$n=18$$ are: 6, 18, 30, 48, 60, 78, 93, 112, 127, 150, 162, 180, 198, 216, 234, 252, which are comfortably within the bound.

The duals of fullerenes show that the constant $$18$$ cannot be improved, but the constant 36 can be. Note that I dropped $$3d_1+2d_2+d_3$$ in the calculation, which can definitely be used to push the bound down by a constant. For large enough $$n$$, $$18n-72$$ is a correct bound and I conjecture that it is the exact value for $$n\ge 13$$.

• Nice! Note that the only place that planarity is used is that every subgraph of a planar graph only has linear number of edges. So the claim is also true for every minor-closed class of graphs (with different constants). Commented Jul 5, 2017 at 17:30
• @TonyHuynh It seems that if every subgraph has average degree at most $\Delta$, then $L(G)\le \Delta^2 n+O(1)$, and no other conditions are needed. Commented Jul 5, 2017 at 18:40

This is just an elaboration on Brendan McKay's beautiful answer, but too long for a comment. The crucial idea is to simplify the problem by generalising it, introducing a maximisation on the indices of the sum, detached from the original planar graph $G$.

For $x = (x_1, \ldots, x_n) \in \mathbb{R}_{\geq 0}^n$ and a multi-graph $H$ with $V(H) \subseteq \{ 1, \ldots, n \}$, let $$L_H(x) := \sum_{ij \in E(H)} \min \{ x_i, x_j \} .$$ For a natural number $d$, let $\mathcal{H}_d$ be the class of all finite multi-graphs $H$ with $V(H) = \{ 1, \ldots, n \}$ (for any $n$) such that $e(H[A]) \leq d(|A|-1)$ holds for any $A \subseteq V(H)$ (in other words, graphs of arboricity at most $d$).

Theorem: For any $x \in \mathbb{R}_{\geq 0}^n$ and any $H \in \mathcal{H}_d$ we have $L_H(x) \leq d(\sum_{i=1}^n x_i - \max_i x_i)$.

Proof: We may assume that $x_i >0$ holds for every $i$. Permute $\{1, \ldots, n\}$ so that $x_1 \geq x_2 \geq \ldots \geq x_n$. Note that $$L_H(x) = \sum_{ij \in E(H) \atop i \, < \, j} x_j$$

Extend the class $\mathcal{H}_d$ slightly by requiring only that $e(H[A]) \leq d(|A| - 1)$ holds when $A = \{ 1, \ldots, k \}$ for some $k$ (that is, $A$ is an initial segment of $\{ 1, \ldots, n\}$). Call this new class $\mathcal{H}_d'$.

Choose $H \in \mathcal{H}_d'$ with $V(H) = \{ 1, \ldots, n \}$ so that $L_H(x)$ is maximum and, subject to this, so that $$R(H) := \sum_{ij \in E(H)} i + j$$ is minimum. We claim that $H$ is a star with center 1. Indeed, if $ij \in E(H)$ and $1 < i < j \leq n$, then we could replace $ij$ by the edge $1j$ and obtain a graph $H'$ with $L(H') = L(H)$ and $R(H') < R(H)$. Trivially $H' \in \mathcal{H}_d'$ as well, hence contradicting our choice of $H$.

Moreover, every $j \in \{ 2, \ldots, n \}$ has degree exactly $d$ in $H$. Otherwise, choose $j$ minimum with $d_H(j) \neq d$. If $d_H(j) > d$, then for $A := \{ 1, \ldots, j \}$ we have $e(H[A]) > d(|A| - 1)$, a contradiction to $H \in \mathcal{H}_d'$. Hence $d_H(j) \leq d-1$. Add an edge $1j$ to $H$. If there is some $k > j$ with $d_H(k) > d$, take a minimum such $k$ and delete one edge $1k$. If there was no such $k$, then the resulting graph $H'$ satisfies $L(H') > L(H)$. If there was such a $k$, then $L(H') = L(H)$ and $R(H') < R(H)$. Either way, $H'$ is easily seen to lie in $\mathcal{H}_d'$ and thus contradicts our choice of $H$.

Now that $H$ is explicitly given, it follows that $$L_H(x) = \sum_{j = 2}^n d x_j .$$ This finishes our proof.

The original statement now follows by taking as $x$ the degree-sequence of a planar graph and noting that $G \in \mathcal{H}_d$ for $d = 3$.