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?


1 Answer 1


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)


You must log in to answer this question.

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