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!

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

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .