Maximum number of vertices in a 5-regular planar graph

301 Views Asked by At

I know how to find the minimum number of vertices in such a graph, as shown below:

Given a planar graph $G$ of order $n$ and size $m$, $n$ and $m$ must satisfy:

$$ m\le 3n-6. $$

Since $\delta(G)=5$, we know $m\ge\displaystyle{\frac{5n}{2}}$. Thus

$$ \begin{align} \frac{5n}{2}\le m&\le 3n-6\\ 5n&\le 6n-12\\ -n&\le -12\\ n&\ge 12 \end{align} $$

However, how do we find the MAXIMUM number of vertices? I understand it would use a similar method, but I can't figure it out for some reason.

1

There are 1 best solutions below

4
On BEST ANSWER

Claim. There is no upper bound on the size of a connected planar 5-regular graph.

Proof.

enter image description here $\square$