A conjecture on planar graphs

Question

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.

What I know about this problem:

• 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). $$

Answer 1

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$.

Answer 2

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$.