# Can't lower bound be improved on number of light edges in planar graph with minimum degree five?

Let an $$i$$-vertex be a vertex of degree $$i$$. Let an $$i, j-$$ edge be an edge joining an $$i-$$vertex to a $$j-$$vertex. Given a plane graph G, let $$e_{i,j}$$ be the number of $$i, j-$$edges of $$G$$.

I found Borodin and Sanders's work through the following paper:

• Oleg V. Borodin, Daniel P. Sanders, On Light Edges and Triangles in Planar Graphs of Minimum Degree Five, Math. Nach. 170 Issue 1 (1994) pp 19–24, doi:10.1002/mana.19941700103.

Theorem Every normal plane map of minimum vertex degree $$5$$ satisfies

$$\frac{14}{3}e_{5,5}+2e_{5,6}\ge 120.$$ The author says the inequality cannot be improved. Since the following graph is constructed with $$e_{5,5}=24$$ and $$e_{5,6}=4$$.

I am very confused about the reason of "cannot be improved". More clearly the author's graph makes me unconvinced. Because we are not clear about the edges outside this local subgraph $$H$$. It is still possible that $$e_{5,5}>24$$ and $$e_{5,6}>4$$ . If this happens, it seems that this lower bound can be improved.

My point is only if we can construct a graph with $$n$$ (arbitrarily large)vertices with minimum degree $$5$$, but $$\frac{14}{3}e_{5,5}+2e_{5,6}= 120.$$ Only then we can say that the coefficient cannot be improved. Otherwise we might even get $$ke_{5,5}+le_{5,6}\ge f(n),$$ where $$k$$ and $$l$$ are all constant, and $$f(n)$$ is function about $$n$$.

After all, there are 5-regular planar graph with $$e_{5,5}=\frac{5n}{2}$$ by doing limited copy of following graph. (Regrettably, I haven't thought of the connected graph example with $$n$$ ($$n>12$$) vertices.It will be better.)

I don’t know if there is a problem with my thinking, I would like to get some guidance.Thanks in advance!

• Did you ask the authors? – Fedor Petrov Mar 22 at 7:30
• Thanks for reminding. Let me think about it first and then I will ask the author. – licheng Mar 22 at 8:38
• My impression is that the authors didn't try to give an infinite family of examples, just a single one. It is obtained by adding a vertex on the outerface and joining it to the 6 half-edges. They do not seem to claim that the coefficients cannot be improved, just that the inequality itself is attained. – Louis Esperet Mar 22 at 15:57
• @licheng But you’ve already asked many other people —- here. – Ilya Bogdanov Mar 22 at 22:58
• @ Ilya Bogdanov Yes, it is true. – licheng Mar 23 at 0:37

Theorem Every normal plane map of minimum vertex degree 5 satisfies $$\frac{14}{3} e_{5,5}+2e_{5,6}≥120.$$ The author says the inequality cannot be improved. Since the following graph is constructed with $$e_{5,5} =24$$ and $$e_{5,6} =4$$.
I think what they mean by "cannot be improved" is that the constant 120 on the right-hand side cannot be increased. The graph they show has $$\frac{14}{3} e_{5,5}+2e_{5,6}=120$$, so we know that 120 is a possible sum.
From your description, maybe you're wondering whether $$\frac{14}{3} e_{5,5}+2e_{5,6}$$ can be bigger than 120--certainly it can be! But it won't always be bigger than 120, since exactly 120 is possible.