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$

1 Answer 1

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$

You must log in to answer this question.

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