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.
Best Answer
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.