Almost All Graphs are Non-Planar

  • Thread starter Thread starter jgens
  • Start date Start date
  • Tags Tags
    Graphs
Click For Summary
SUMMARY

The discussion focuses on proving that almost all graphs are non-planar, leveraging Kuratowski's Theorem, which states that a graph is planar if it does not contain a subgraph homeomorphic to K5 or K3,3. The main approach involves analyzing the probability Pn that a random graph on n vertices is non-planar and demonstrating that limn -> ∞ Pn = 1. A suggestion is made to partition the vertices into groups of five to increase the likelihood of encountering at least one K5 subgraph as n grows large.

PREREQUISITES
  • Kuratowski's Theorem
  • Graph theory fundamentals
  • Understanding of homeomorphism in graphs
  • Probability theory related to random graphs
NEXT STEPS
  • Study the implications of Kuratowski's Theorem on graph planarity
  • Explore random graph theory, particularly Erdős–Rényi model
  • Investigate methods for identifying subgraphs homeomorphic to K5 and K3,3
  • Learn about probabilistic methods in combinatorial graph theory
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in graph planarity and random graph behavior.

jgens
Gold Member
Messages
1,575
Reaction score
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
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?
 

Similar threads

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