Return to Revisions

Regarding Question 3, 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 new vertex $v_f$ inside each face $f$ of $I$, and making $v_f$ adjacent to all vertices of $f$. Since $I$ has $12$ vertices and $20$ faces (each of which is a triangle), $G$ is a planar graph with $32$ vertices, $20$ of which have degree $3$, and $12$ of which have degree $10$. 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$.