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



A conjecture on planar graphs
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$.


