Return to Answer

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

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

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.

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.

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

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.

The duals of fullerenes show that the constant 18 cannot be improved, but the constant 36 probably can be.

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.

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.