Almost All Graphs are Non-Planar

  • Thread starter jgens
  • Start date
  • Tags
    Graphs
In summary, Kuratowski's Theorem states that a graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3,3. To prove that almost all graphs are not planar, one can use the fact that a random graph on n vertices is not planar with a probability of 1 as n approaches infinity. This can be shown by considering the case where n is divisible by 5 and dividing the vertices into collections of 5, where the probability of getting at least one K5 is high as n becomes large.
  • #1
jgens
Gold Member
1,593
50

Homework Statement



Prove that almost all graphs are not planar graphs.

Homework Equations



Kuratowski's Theorem

The Attempt at a Solution



Kuratowski's Theorem states that a graph is planar if and only if it does not contain a subgraph homeomorphic to K5 or K3,3. Therefore, if I can show almost all graphs have subgraphs homeomorphic to K5 or K3,3, this would complete the proof.

My thought on this was to let Pn denote the probability that a random graph on n vertices is not planar and then show limn -> ∞Pn = 1. However, I need some help on how to show which graphs on n vertices contain subgraphs homeomorphic to K5 or K3,3. Can anyone give me a nudge in the right direction?

Thanks!
 
Physics news on Phys.org
  • #2
I think you can hit this with a sledgehammer. Consider just the case where n is divisible by 5 and divide up the vertices into collections of 5. Can you show that if n is big the probability is high that you get at least one K5?
 

FAQ: Almost All Graphs are Non-Planar

Why are almost all graphs non-planar?

Almost all graphs are non-planar because a graph is considered planar if it can be drawn on a plane without any of its edges intersecting. As the number of vertices and edges in a graph increases, the likelihood of it being non-planar also increases.

Can you give an example of a non-planar graph?

One example of a non-planar graph is the complete graph, where every vertex is connected to every other vertex. This graph cannot be drawn on a plane without its edges intersecting.

Are there any benefits to studying non-planar graphs?

Yes, studying non-planar graphs can help us better understand the complexity of different types of networks and how they behave. It also has practical applications in fields such as computer science and engineering.

Is there a way to determine if a graph is non-planar?

Yes, there are several algorithms and theorems that can be used to determine if a graph is non-planar. One common method is to check for the presence of a subgraph known as the Kuratowski graph, which is non-planar.

Can a non-planar graph be converted into a planar graph?

In some cases, a non-planar graph can be redrawn or transformed in a way that makes it planar. However, this is not always possible, and it may require adding additional edges or vertices to the graph. In general, it is easier to prove that a graph is non-planar than to find a way to make it planar.

Similar threads

Strong Induction, Tangled Graph
Replies
3
Views
3K
How to construct a graph with girth = twice the diameter + 1
Replies
2
Views
2K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
Graph Theory: Extremal Problem
Replies
1
Views
1K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
Replies
3
Views
2K
I Finding if a subgraph of a minimal non-planar graph is maximal planar
Replies
1
Views
1K
Prove that there exists a graph with these points such that....
Replies
2
Views
1K
Analysing the Isomorphism between G3 & K3,3 and Planarity of Gn
Replies
3
Views
2K
Hamiltonian Path - Induction Proof
Replies
4
Views
3K
MHB Proving a graph is planar/nonplanar
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top