Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal planar graph.

My idea in figuring this out would be by taking a minimal non-planar graph and then removing one edge, specifically the one that crosses another edge making the graph non-planar. That would obviously make the graph planar, but I said it wouldn't be a maximal planar graph because with the removal of one edge, we're left with two vertices that originally connected that edge and now aren't connected to other parts of the graph such that those connections would still make it planar.

I'm wondering if my explanation is a sufficient enough proof or if I'm missing something. Thank you in advance.

  • $\begingroup$ I thought a minimal non-planar graph is a non-planar graph every proper subgraph is planar. See homepages.math.uic.edu/~culler/talks/planargraphs.pdf $\endgroup$
    – saulspatz
    Jun 22, 2019 at 2:30
  • $\begingroup$ That's true, but I was just saying that if you take out an edge the graph will be planar but not maximal planar since you can still attach edges to the two vertices of the edge you removed without making the graph non-planar. $\endgroup$
    – SYoshi
    Jun 22, 2019 at 22:30

1 Answer 1


If $G=K_{3,3}$, then deleting any edge $e$ gives a planar graph which is not maximal planar, since we can join two vertices in the same bipartition set, and still have a planar graph. On the other hand, if $G=K_5$, then deleting any edge gives a maximal planar graph, so there doesn't seem to be any positive statement you can make.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.