Recently, I read one literature and saw a property about the planar graph. I thought about it for a long time without thinking out the reason:
Let $G$ be a planar graph. Then at least one of $G$ and its
dual graph $G^*$ has a vertex $v$ of degree at most 3.
I know some conclusions that may be useful.
- Every planar graph has a vertex of degree at most $5$.
- The number of edges in a maximal planar graph is $3n-6$.
Definition of dual graph:
Given a plane graph $G$, one can define a second graph $G^∗$ as follows. Corresponding to each face $f$ of $G$ there is a vertex $f^∗$ of G∗ , and corresponding to each edge $e$ of $G$ there is an edge $e^∗$ of $G^∗$ . Two vertices $f^∗$ and $g^∗$ are joined by the edge $e^∗$ in $G^∗$ if and only if their corresponding faces $f$ and $g$ are separated by the edge $e$ in $G$.
Observe that if e is a cut edge of G, then $f = g$, so $e^∗$ is a loop of G∗; conversely,if e is a loop of $G$, the edge $e^∗$ is a cut edge of $G^∗$. The graph $G^*$ is called dual of G.
Best Answer
Let $n$ be the number of vertices of $G$, $m$ the number of edges of $G$, and $r$ the number of faces of $G$. We use the notation $\mathcal{E}(f)$ for the number of edges on the face $f$.
We will assume that $G^*$ has no vertex of degree $3$ or less, and prove that $G$ must then have a vertex of degree at most $3$.
If $G^*$ has no vertex of degree $3$ or less, than every face of the original graph $G$ has at least $4$ edges on its boundary. Since every edge appears twice on a face boundary (either once on two different faces, or twice on one face if it is a cut edge), we get that:
$$\sum_{f\text{ a face of $G$}} \mathcal{E}(f) = 2m$$
We have assumed that $G^*$ has minimum degree at least $4$, so this gives:
$$2m = \sum_{f\text{ a face of $G$}} \mathcal{E}(f) \geq 4r$$
By substituting $r\leq \frac{m}{2}$ into Euler's Formula ($n-m+r = 2$), we get that:
$$2 = n-m+r \leq n-m + \frac{m}{2}$$
Rearrange this to bound the number of edges as $m\leq 2n-4$.
Since $2m = \sum_{v\in V(G)}d(v)$, we get that the sum of the degrees is bounded by:
$$\sum_{v\in V(G)}d(v) = 2m \leq 4n-8 < 4n$$
The sum of the degrees of $G$ is less than $4n$, so the average degree of $G$ is less than $4$ (the average degree is the sum of the degrees divided by $n$). This means there is at least one vertex with degree less than $4$, completing the proof.