Specifically for planarity, it's pretty easy to convince yourself that K5 and K3,3 are minimally non-planar. You don't come out with a rigorous proof but you do

Specifically for planarity, it's pretty easy to convince yourself that K5 and K3,3 are minimally non-planar. You don't come out with a rigorous proof but you do get an intuitive feel. With a decent motivating example it's accessible to kids.