Math 2.0

Combinatorics Planar graphs, embeddings, minors Theorem

Kuratowski's theorem

Builds on SubgraphPlanar graphK5 and K3,3 are not planar

Statement

A subdivision of a graph HH is a graph that HH gives when some edges are replaced by paths with new inner vertices. Let GG be a finite graph. Then GG is planar if and only if no subgraph of GG is a subdivision of K5K_5 or of K3,3K_{3,3}.

Remarks

One direction is easy: a subdivision of a nonplanar graph is nonplanar, and K5K_5 and K3,3K_{3,3} are not planar. Wagner's theorem is a related result: a finite graph is planar if and only if it has neither K5K_5 nor K3,3K_{3,3} as a minor.

History

Kazimierz Kuratowski published the theorem in 1930. Orrin Frink and Paul Smith proved it independently in the same year, but they did not publish their proof. Lev Pontryagin reportedly proved it around 1927, and in the Soviet Union it was also known under his name.

Reading path

To understand this page from the ground up, read these 12 pages in order. The foundations come first.

Show the path as a graph
Complete bipartite graph, example, no evidence levelComplete bipartite gr…exampleComplete graph, example, no evidence levelComplete graphexampleGraph, definition, no evidence levelGraphdefinitionPlanar graph, definition, no evidence levelPlanar graphdefinitionSubgraph, definition, no evidence levelSubgraphdefinitionWalk, definition, no evidence levelWalkdefinitionReachability, definition, no evidence levelReachabilitydefinitionConnected graph, definition, no evidence levelConnected graphdefinitionEuler's formula for planar graphs, statement, no evidence levelEuler's formula for p…statementEdge bound for planar graphs, statement, no evidence levelEdge bound for planar…statementK5 and K3,3 are not planar, statement, no evidence levelK5 and K3,3 are not p…statementKuratowski's theorem, statement, no evidence levelKuratowski's theoremstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complete bipartite graph example
  2. Complete graph example
  3. Graph definition
  4. Planar graph definition
  5. Subgraph definition
  6. Walk definition
  7. Reachability definition
  8. Connected graph definition
  9. Euler's formula for planar graphs statement
  10. Edge bound for planar graphs statement
  11. K5 and K3,3 are not planar statement
  12. Kuratowski's theorem statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Kuratowski's_theorem, Statement
About this page
Tag0J6G5NJC5R
URIm2://0J6G5NJC5R
Kindstatement, theorem
WritingW0 stub
MSC05C10
StatusThis copy of the site has no build data. Run m2 status 0J6G5NJC5R.
UsesSubgraph, Planar graph, K5 and K3,3 are not planar
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.