4
$\begingroup$

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

enter image description here

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.

enter image description here

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

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

$\endgroup$
5
  • 1
    $\begingroup$ Did you ask the authors? $\endgroup$ – Fedor Petrov Mar 22 at 7:30
  • $\begingroup$ Thanks for reminding. Let me think about it first and then I will ask the author. $\endgroup$ – licheng Mar 22 at 8:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Louis Esperet Mar 22 at 15:57
  • $\begingroup$ @licheng But you’ve already asked many other people —- here. $\endgroup$ – Ilya Bogdanov Mar 22 at 22:58
  • $\begingroup$ @ Ilya Bogdanov Yes, it is true. $\endgroup$ – licheng Mar 23 at 0:37
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for your reply, I think your answer helped me understand what the author meant. $\endgroup$ – licheng Mar 23 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.