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). $$
  • 1
    $\begingroup$ 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 $\endgroup$ Jul 4, 2017 at 18:26
  • 1
    $\begingroup$ 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)$. $\endgroup$ Jul 4, 2017 at 19:32
  • $\begingroup$ 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.) $\endgroup$ Jul 8, 2017 at 13:36
  • $\begingroup$ 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. $\endgroup$ Jul 8, 2017 at 13:44

2 Answers 2


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

  • 1
    $\begingroup$ 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). $\endgroup$
    – Tony Huynh
    Jul 5, 2017 at 17:30
  • $\begingroup$ @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. $\endgroup$ 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$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .