Return to Revisions

Here is a proof that $f(n)=30$ for all $n \geq 32$. Let $I$ be the icosahedron. Let $G$ be obtained from $I$ by adding a degree-$3$ vertex inside each face of $I$. Then $G$ is a planar graph with $32$ vertices, $20$ of which have degree $10$, and $12$ of which have degree $3$. Since no two degree-$3$ vertices are adjacent in $G$, every edge $e$ of $G$ satisfies $D(e) \geq 30$. To get examples for larger values of $n$, we can apply the above construction to any planar triangulation with minimum degree $5$.