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

  • Thread starter Thread starter Superyoshiom
  • Start date Start date
  • Tags Tags
    Graph Graph theory
Click For Summary
In the discussion, the focus is on determining whether the removal of an edge from a minimal non-planar graph can result in a maximal planar graph. The initial idea suggests that removing an edge that causes a crossing would make the graph planar but not maximal, as it leaves two vertices disconnected from other parts of the graph. However, a counterpoint is raised, arguing that the vertices should still be connected through alternative paths after the edge removal. The need for a formal proof and proper definitions in graph theory is emphasized, highlighting the complexity of the topic. Overall, the discussion revolves around the intricacies of edge removal and its impact on graph planarity.
Superyoshiom
Messages
29
Reaction score
0
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.
 
Mathematics news on Phys.org
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.
Superyoshiom said:
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
5K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Proving a graph not simple and planar after adding edges
  • · Replies 4 ·
Replies
4
Views
2K
Algorithm to find the minimum spanning tree on a planar graph
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
Prove the decomposition of a graph w/ even edges produce a 2-path set
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Interesting graph theory problem
  • · Replies 1 ·
Replies
1
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
2K