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.



Product of vertex degrees of an edge in a planar graph
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.


