Return to 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.

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.

Regarding Question 3, here is a proof that $f(n)=30$ for all $n \geq 42$. 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 40$, we are done.

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.

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$.

Regarding Question 3, here is a proof that $f(n)=30$ for all $n \geq 42$. 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 40$, we are done.