In each case, give the values of r, e, or v (whichever is not given) assuming that the graph is planar. Then either draw a connected, planar graph with the property, if possible, or explain why no such planar graph can exist.
I'm stuck on this one: 17 regions and every vertex has degree 5. Using Euler's formula, I believe it would be v – 34 + 17 = 2 with v = 19 which gives a valid answer because using 3V-6 theorem, 57 – 6 >= 34? But the answer is that it's not possible, why?
Best Answer
$v=19$ can't be true, since 5 is odd, and every graph has an even number of odd degree vertices by handshake theorem (Also note that $e=5v/2$ must be an integer)
We do know that $e=5v/2$, so we can plug this into Euler's formula and get: $$v - 5v/2+17=2$$ $$\implies v=10$$
So $v=10$. But since $G$ is assumed to be planar, we know that $e \leq 3v-6=24$. Since $G$ has 10 vertices, each with degree 5, $e=25$, so no such planar graph exists.