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}\).

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email