$\begingroup$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?
$\endgroup$22 Answers
$\begingroup$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?
$\endgroup$$\begingroup$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.
$\endgroup$
