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

In summary, when given a minimal non-planar graph G, we need to remove an edge e to make G' a maximal planar graph. This can be achieved by removing the edge that crosses another edge in the graph, making it planar. However, to prove that G' is a maximal planar graph, we need to formalize the explanation by using definitions from graph theory and showing that the vertices that were originally connected via the removed edge are still connected via another path.
  • #1
Superyoshiom
29
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
  • #2
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.
 

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

1. What is a subgraph?

A subgraph is a smaller graph that is contained within a larger graph. It consists of a subset of the vertices and edges of the original graph.

2. What is a minimal non-planar graph?

A minimal non-planar graph is a graph that cannot be drawn on a flat surface without any edges crossing. It has the minimum number of edges needed to make it non-planar.

3. What does it mean for a subgraph of a minimal non-planar graph to be maximal planar?

A subgraph of a minimal non-planar graph is maximal planar if it can be drawn on a flat surface without any edges crossing, and it has the maximum number of edges possible for a planar graph with the same number of vertices.

4. How do you determine if a subgraph of a minimal non-planar graph is maximal planar?

To determine if a subgraph of a minimal non-planar graph is maximal planar, you can use the Kuratowski's theorem. This theorem states that a graph is non-planar if and only if it contains a subgraph that is a subdivision of either K5 or K3,3. If the subgraph does not contain a subdivision of these graphs, then it is maximal planar.

5. Why is it important to find if a subgraph of a minimal non-planar graph is maximal planar?

It is important to find if a subgraph of a minimal non-planar graph is maximal planar because it helps in understanding the structure and complexity of the original graph. It also has applications in various fields such as network design, circuit design, and graph theory.

Back
Top