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

  • Context: Undergrad 
  • Thread starter Thread starter Superyoshiom
  • Start date Start date
  • Tags Tags
    Graph Graph theory
Click For Summary
SUMMARY

The discussion centers on determining whether the removal of an edge from a minimal non-planar graph G results in a maximal planar graph G'. Specifically, the participant proposes that removing an edge e, which crosses another edge, would render G planar but not maximal planar due to the disconnection of two vertices. However, a counterpoint is raised, asserting that the vertices remain connected through alternative paths after the edge's removal. This highlights the need for a formal proof in graph theory to validate the conditions under which G' can be classified as maximal planar.

PREREQUISITES
  • Understanding of graph theory concepts, specifically planar and non-planar graphs.
  • Familiarity with the definitions of maximal planar graphs.
  • Knowledge of edge connectivity and its implications in graph structures.
  • Basic skills in formal proof writing within mathematical contexts.
NEXT STEPS
  • Study the definitions and properties of maximal planar graphs in graph theory.
  • Explore the concept of edge connectivity and its role in graph classifications.
  • Learn about formal proof techniques in mathematics, particularly in graph theory.
  • Investigate examples of minimal non-planar graphs and their transformations into planar graphs.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in planar graph properties and proof methodologies.

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.
 

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
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
Undergrad Graph Theory: (proof)conditions for Euler Circuit in Digraph
  • · Replies 1 ·
Replies
1
Views
3K
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
Undergrad Find Two Equal Length Paths in a Tree Graph
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K