(a) A connected planar graph $G$ has $20$ faces, and every vertex of $G$ has degree exactly $4$.
Find the number of vertices of $G$.
(b) A connected planar graph has $26$ faces and $V$ vertices, and all its vertices have the same degree. What are all possible values of $V$?
I tried drawing the diagram for part a, but it got too big and I'm not sure how to do part b. Any help is appreciated.
Best Answer
There's no need to draw anything for $a$. If there are $v$ vertices, all of degree $4$, there are $2v$ edges. By Euler's relation, $v+20-2v=2$, which solves to $v=18$.
Similarly, for (b) let there be $v$ vertices of degree $d$; there are $vd/2$ edges and $v+26-vd/2=2$ or $24=v(d/2-1)$. Obviously we must also have $d\le v-1$, and so we have $$(v,d)\in\{(12,6),(16,5),(24,4),(48,3)\}$$ The $(12,6)$ case is also eliminated by a theorem saying that a planar graph can have at most $2v-4$ faces. So the graph may have $16,24,48$ vertices.