Determine all maximal planar graphs, where one-third of their vertices have degree $3$, one-third have degree $4$, and one third have degree $5$.

Question

To do this, I have $\frac {1}{3}n = \deg 3$, $\frac {1}{3}n = \deg 4$, and $\frac {1}{3}n = \deg 5$. I also know that $e=3n-6$ where $e$ is the number of edges and $n$ is the number of vertices. I also know that the sum of $\frac {1}{3}n$ of degree $3 + \frac {1}{3}n$ of degree $4 + \frac {1}{3}n$ of degree $5 =2e$.However, I still don't know how to find $n$ and how do I determine all the maximal planar graphs?

Answer 1

Maximal planar graphs are triangulated, so we know that each face has degree $3$. By the handshaking lemma (for faces), we conclude that $$3F = 2E,$$ where $F$ and $E$ are the total number of faces and edges respectively. Likewise, the handshaking lemma (for vertices) tells us that $$\frac{3V}{3} + \frac{4V}{3} + \frac{5V}{3} = 4V = 2E.$$ Finally, Euler's theorem $$V - E + F = 2,$$ together with the previous relations tell us that $V=6$.

So we must have an order $6$ graph with $2$ vertices of degree $3$, $2$ vertices of degree $4$, and $2$ vertices of degree $5$. Clearly the degree $5$ vertices must be connected to every other vertex, and you can easily fill in the remaining blanks. You should find that there is a unique maximally planar graph satisfying these requirements.