Let $G$ be a planar graph, which we may assume to be a triangulation, with vertex set $V$ and edge set $E$. Suppose the minimum vertex degree is at least 3, and suppose any two distinct edges share at most one vertex.

Definition. Given an edge $e \in E$ with vertices $v_1$ and $v_2$, define $D(e) = \mathrm{deg}(v_1). \mathrm{deg}(v_2)$, the product of the degrees of the vertices of $e$.

I have been calling this quantity the density of the edge $e$, but:

Question 1: Has this quantity $D(e)$ been previously studied? Does it already have a name?

This quantity is likely to have properties akin to those of the weight $w(e) = \mathrm{deg}(v_1) + \mathrm{deg}(v_2)$. It is a result of Borodin [1] that every planar graph under consideration has a $(5,6)$ edge, a $(4,7)$ edge, a $(3,10)$ edge, or an edge with degrees less than one of these. As a direct consequence of this:

Theorem. Every planar graph $G$ has an edge $e$ with $D(e) \leq 30$.

Question 2: Is there a reference for this result?

I am interested in the values of $D$ that can and must appear in a graph with $n$ vertices.

Definition. Let $f(n)$ be the least natural number $N$ such that every planar graph with $n$ vertices has an edge $e$ with $D(e) \leq N$.

The theorem above implies that for all $n$, $f(n) \leq 30$. For example, $f(4) = 9$ because the only possible graph is the tetrahedron with all vertices degree 3, and so each edge has $D(e) = 9$. I think $f(5)=12$, $f(6)=f(7)=f(8)=16$ and $f(12)=25$. I suspect that $f(n)=30$ for all $n \geq 32$.

Question 3: Has this quantity $f(n)$ been studied for any or all $n$?

Thanks for any help.

[1] Borodin, O. V., Joint generalization of the theorems of Lebesgue and Kotzig on the combinatorics of planar maps. (Russian) Diskret. Mat. 3 (1991), no. 4, 24–27.

  • 1
    $\begingroup$ Agreed up to $f(7)$. However, $f(8)=18$. Continuing, $f(9)=f(10)=f(11)=20$, $f(12)=25$, $f(13)=21$, $f(14)=f(15)=f(16)=f(17)=25$. It gets slower after that. $\endgroup$ Oct 26 at 13:21
  • 1
    $\begingroup$ These lower bounds are precise for planar graphs with minimum degree at least 4: $f(18)\ge 25$, $f(19)\ge 25$, $f(20)\ge 25$, $f(20)\ge 25$. $\endgroup$ Oct 26 at 13:29
  • 1
    $\begingroup$ To get $f(8)\ge 18$, start with a cube properly coloured black and white. Then join every pair of white vertices that lie on the same face. $\endgroup$ Oct 26 at 13:30
  • 1
    $\begingroup$ For minimum degree at least 5, the best value achieved is 25 for $21,\ldots,31$ and $f(32)\ge 30$. $\endgroup$ Oct 26 at 13:40
  • 1
    $\begingroup$ For $f(13)=21$, take the octahedron (6 vertices and 8 faces) and insert a new vertex of degree 3 into all but one of the faces. That gives some vertices of degree 7 adjacent to degree 3 and no smaller products. There is no planar triangulation with 13 vertices and minimum degree 5; I'm not sure what the quickest proof is. $\endgroup$ Oct 27 at 0:45

Regarding Question 3, here is a proof that $f(n)=30$ for all $n \geq 40$. Let $H$ be a $2$-connected planar graph with minimum degree $5$. Let $G$ be obtained from $H$ by adding a new vertex inside each face of $H$, and making it adjacent to all vertices of the face. Let $V(G)=X \cup Y$, where $X=V(H)$, and $Y$ are the newly added vertices. Since $H$ has minimum degree $5$, $\deg_G(x) \geq 10$ for all $x \in X$. Moreover, $\deg_G(y) \geq 3$ for all $y \in Y$ and no two vertices of $Y$ are adjacent. Thus, $\deg(u)\deg(w) \geq 30$ for all $uw \in E(G)$. Note that $G$ is a planar graph with $|V(H)|+|F(H)|$ vertices, where $F(H)$ is the number of faces of $H$. By Euler's formula, $|V(G)|=|E(H)|+2$. Since there is a $2$-connected planar graph with minimum degree $5$ and $m$ edges for all $m \geq 38$, we are done.

  • $\begingroup$ OK thanks. I got the stellated icosahedron and also you can do this with a dodecahedron and add a degree 5 vertex inside each face. Suspected what you say for $n>32$ but wasn't totally sure there always exists an $n$-vertex planar graph with minimum degree 5. $\endgroup$ Oct 26 at 14:56
  • 1
    $\begingroup$ There is always an $n$-vertex planar graph with minimum degree 5 for all $n \geq 14$, but for the construction, we actually care about the number of edges. I updated the answer and the bound (32 became 40). $\endgroup$
    – Tony Huynh
    Oct 27 at 2:17
  • 1
    $\begingroup$ (I didn't work out the details, feel free.) A dual fullerene has all vertices of degree 6 except for 12 of degree 5. They exist for $n\ge 12$ except $n=13$. Add a new vertex into each face incident with each vertex of degree 5 and at least 4 of the 6 faces incident with each vertex of degree 6. This allows a lot of freedom. $\endgroup$ Oct 27 at 11:25
  • $\begingroup$ OK thanks, this is helpful. Is it true that for large $n >>32$ there will exist examples with 12 degree 5 vertices, all "far apart" from each other in some sense, and $n-12$ degree 6 vertices? $\endgroup$ Oct 29 at 15:07
  • $\begingroup$ @GrantLakeland If all the vertices of degree 5 are non-adjacent, those are the duals of IPR fullerenes. (IPR=independent pentagon rule, a mnemonic from chemistry). They exist for $n=32$ and all $n\ge 37$. However the construction I gave doesn't rely on non-adjacent degree 5s. The question is whether it fills the gap between 32 and Tony's general result. $\endgroup$ Oct 30 at 12:25

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.