• Support PF! Buy your school textbooks, materials and every day products Here!

Almost All Graphs are Non-Planar

  • Thread starter jgens
  • Start date
  • #1
jgens
Gold Member
1,580
49

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!
 

Answers and Replies

  • #2
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
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?
 

Related Threads on Almost All Graphs are Non-Planar

  • Last Post
Replies
1
Views
897
Replies
3
Views
2K
  • Last Post
Replies
3
Views
870
  • Last Post
Replies
0
Views
3K
Replies
0
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
833
  • Last Post
Replies
12
Views
2K
Top