What is minimum number of edges should be removed from $K_6$ to get planar graph?

Question

What is minimum number of edges should be removed from $K_6$ to get planar graph?

It is easy to show it just with picture.. but is it possible to prove it analytically?

Answer 1

Hint: What is the maximum number of edges in an $n$-vertex planar graph? How many edges are in $K_6$? How do these numbers compare?

Answer 2

All the faces must be "triangles" (If a face is not a $3$ cycle then draw in a "diagonal"). So $3f=2e$.

Planar ? ... Euler's formula ... $v-e+f=2$. ... $K_6$ : Also $v=6$.

Solve these $3$ equations ( $3 \times (v-e+f=2)$ etc ...) gives $e=12$.

$K_6$ has $15$ edges ... so we need to remove $\color{red}{3}$ edges.