Teorema de Kuratowski
En teoria de grafos, la teorema de Kuratowski, desenrollat pel matemàtic polac Kazimierz Kuratowski, és una caracterisació dels grafos planars.
Definició
[editar | editar còdic]
Una subdivisió elemental d'un grafo resulta d'insertar vèrtiços en les arestes (per eixemple, canviant •——• per •—•—•). Una formulació equivalent a esta teorema és:
Eixemple
[editar | editar còdic]¿El grafo K6 complet pot ser pla?
Si s'elimina un vèrtiç de K6 i totes les arestes que ho unixen en el restant de vèrtiços, es pot observar que el grafo K6 conté com subgrafo un K5. Per la Teorema de Kuratowski es pot afirmar que el grafo K6 no és planar.
en:Planar graph#Kuratowski's and Wagner's theorems
- Este artícul conté una traducció derivada de «Teorema de Kuratowski» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.