I want to show that there exists only one 4-regular maximal planar graph .So, I know that the maximal planar graph has an upper bound for the size of a planar graph ,that's, $m=3n-6$ ($n$ is the order of the graph )Using this bound we can also see that with $ n=4$ or more the degree of each vertex is at least $3$ but how to put all these facts together to prove the desired result ?
[Math] There exists only one 4-regular maximal planar graph
graph theory
Best Answer
Let $G$ be a $4$-regular maximal planar graph. By Handshaking lemma $$2m = \sum_{v \in V(G)} \deg v = 4n.$$ So $2n = m = 3n - 6$, therefore $n = 6$. Then $\overline{G}$ is $1$-regular graph on $6$ vertices, that is $3K_2$. Then $G \cong \overline{3K_2}$ is the only $4$-regular maximal planar graph.