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?
graph theory
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?
Best Answer
You probably learned that for a simple connected planar graph,
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)