Der Graph ist vollständig, also ist es gleich welche Kante entfernt wird. Zeichne den resultierenden Graphen so, dass sich keine Kante überschneidet.
Alternativ kannst du auch nachweisen, dass der resultierende Graph keinen Teilgraphen besitzt, der Unterteilungsgraph von K5 oder K3,3 ist. Ersteres kann wegen der Anzahl der Kanten nicht sein, letzteres nicht wegen Anzahl der Ecken. Nach dem Satz von Kuratowski ist der Graph dann planar.