Skip to main content
3 of 7
added 66 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

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=17$ are: 6, 18, 30, 48, 60, 78, 93, 112, 127, 150, 162, 180, 198, 216, 234, which are comfortably within the bound.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147