Critical nonplanar and edge replacement
Task number: 4060
Let \( G \) be a non-planar graph such that \( G - e \) is planar for each edge of \( e \) of the graph \( G \). Does then \( G \) necessarily contain an edge \( e \) such that \( G-e \) is the maximum planar graph, i.e. by adding any edge \( f \), the graph \( G-e + f \) will be non-planar?
Hint
Seek for an counterexample.
Solution
The statement does not hold. A counterexample is e.g. the graph \(K_{3{,}3}\).
