dmoi Exercise 4.3.15: Explain why we cannot use the same sort of proof we did in Exercise 4.3.14 to prove that the graph below is not planar. Then explain how you know the graph is not planar anyway.
Solution:
$v=11,e=25,g=3$, if the graph is planar, $v-e+f=2⇒f=16$. Notice that $48=gf≤2e=50$ is satisfied, so we cannot use the same sort of proof we did in Exercise 4.3.14 to prove that the graph below is not planar.
If the graph is planar, the graph in Exercise 4.3.14 is its subgraph so would be planar too, contradiction. Therefore the graph is not planar.
