Proof
(related to Proposition: A Necessary Condition for a Graph with Shortest Cycles to Be Planar (II))
- By hypothesis, $k\ge 3$ is a positive integer and $G(V,E)$ is a simple, biconnected, planar graph with $|E|$ edges and $|V|$ vertices and shortest cycle length $k.$
- By a necessary condition for $G$ to be planar, $$\begin{align}|E|\le\frac{k}{k-2}(|V|-2).\tag{*}\label{E21118a}\end{align}$$
- Suppose, the degree of each vertex of $G$ is $\ge k+3.$
- With the handshaking lemma for graphs, it follows $2|E|=\sum_{v\in V}\deg(v)\ge|V|\cdot (k+3),$ or
$$\begin{align}|E|\ge|V|\frac{k+3}{2}.\tag{**}\label{E21118b}\end{align}$$
- Combining $(\ref{E21118a})$ and $(\ref{E21118b}),$ we obtain $$|V|\frac{k+3}2\le |E|\le \frac{k}{k-2}(|V|-2).$$
- This is equivalent to $$|V|(k^2+k-6)\le 2k|V|-4k.$$
- Since $k\ge 3,$ we get for $k=3$: $6|V|\le 6|V|-12$ which is false.
- By contradiction, $G$ contains a vertex $v$ of degree $\deg(v)\le k+2.$
∎
Thank you to the contributors under CC BY-SA 4.0! 
- Github:
-
