I Finding if a subgraph of a minimal non-planar graph is maximal planar

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 trying to figure 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.
 

fresh_42

Mentor
Insights Author
2018 Award
10,724
7,339
You will have to formalize it. I'm no expert in graph theory so I do not have the definitions in mind, but they should be used here.
we're left with two vertices that originally connected that edge and now aren't connected to other parts of the graph
Why that? You removed a crossing, so the vertices should still be connected via another path.
 

Want to reply to this thread?

"Finding if a subgraph of a minimal non-planar graph is maximal planar" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top