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

  • #1
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.
 

Answers and Replies

  • #2
13,545
10,631
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.
 

Related Threads on Finding if a subgraph of a minimal non-planar graph is maximal planar

  • Last Post
Replies
7
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
2K
Replies
2
Views
475
  • Last Post
Replies
3
Views
2K
Replies
1
Views
2K
Replies
2
Views
191
Replies
4
Views
858
  • Last Post
Replies
2
Views
1K
Top