0
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

$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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .