# Product of vertex degrees of an edge in a planar graph

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.

• 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. Oct 26 at 13:21
• 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$. Oct 26 at 13:29
• 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. Oct 26 at 13:30
• For minimum degree at least 5, the best value achieved is 25 for $21,\ldots,31$ and $f(32)\ge 30$. Oct 26 at 13:40
• 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. 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.
• 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. Oct 26 at 14:56
• 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). Oct 27 at 2:17
• (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. Oct 27 at 11:25
• 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? Oct 29 at 15:07
• @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. Oct 30 at 12:25