0
$\begingroup$

Why cannot a simple connected planar graph G with 10 vertices and 25 edges have 17 faces?

by using Euler’s formula, $n−m+f = 10 -25 +17=2$.

How can I show that it does not?

$\endgroup$
2
$\begingroup$

You probably learned that for a simple connected planar graph,

$$ \# \, edges\leq 3(\#\,vertices)-6$$

Which shows that your graph is impossible, since the following inequality is clearly false: $$ 25 \leq 3(10)-6 = 24 $$ Otherwise, a proof of the above inequality can be found on the internet as a consequence of Euler's Formula (or from another answerer on this post, or from me this afternoon)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.