Grafo lau
Grafo teorian grafo lau deritzo planoan marraztu daitekeen grafo bati, ertzak haien artean gurutzatu gabe. Alboko adibideetan K5 eta K3,3 gutxieneko grafo ez lauak dira, eta horietatik abiatuta zehaztu daitezke gainerako grafo ez-lauen ezaugarriak.
Edozein grafo lau esferaren gainean marraztu daiteke, baita alderantziz.
| Adibideak | |
|---|---|
| Grafo laua | Grafo ez-laua |
 |
 |
 |
 |
Kuratowskiren Teorema
Kazimierz Kuratowski matematikari poloniarrak grafo lauen karakterizazio bat aurkitu zuen, Kuratowskiren teorema bezala ezagutzen dena.
Beste irizpide batzuk
Zaila da Kuratowskiren teorema erabiltzea grafo bat zaila den azkar erabakitzeko. Arazo hau konpontzeko algoritmo azkar bat dago: a ertz eta n erpin dituen grafo bat izanik, posiblea da grafoa laua den zehaztea Eulerren formularekin.
Eulerren formula
Eulerren formulak dio grafo lau lotu batek honakoa betetzen duela: Txantiloi:Teorema Aurreko adibideetan, lehen grafo lauan (K6-a) honako hauek ditugu: v = 6, a = 7 eta c = 3. Bigarren grafoa ertz-elkargunerik gabe marraztuz, v = 4, a = 6 eta c = 4 izango genuke, grafoa laua izanik. Ohartu Eulerren formula poliedro sinpleetarako ere baliagarria da. Ez da kasualitatea: poliedro sinple bakoitza grafo lau eta lotu gisa ikus daiteke, poliedroaren erpinak grafoaren erpin gisa erabiliz, eta poliedroaren ertzak grafoaren ertz gisa. Grafo lauaren aurpegiak edo eskualdeak poliedroaren aurpegiak dira. Adibidetakoko bigarren grafo laua, adibidez, tetraedro bati dagokio.
Beste irizpide batzuk ondoko bi teoremak dira: Txantiloi:Teorema Hau da, n erpin dituen grafo lauak, izanik, gehienez ertz izango ditu. Txantiloi:FrogaTxantiloi:Teorema
Txantiloi:Froga 1 teorematik ondorioztatzen dugu K5 ez dela laua, 5 ertzeko grafo lau batek gehienez 9 ertz izan ditzakelako, baina K5-ek 10 ertz dituenez ez da laua. K3,3-ren kasuan, 6 erpin ditu eta ez du 3 luzerako ziklorik, baina 9 ertz dituenez, 2. teoremak dio ezin dela laua izan.
Ohartu teorema hauek norabide bakarreko inplikazioarekin adierazita daudela, eta ez bi norabideetan. Hori dela eta, bakarrik erabili daitezke grafo bat laua ez dela ziurtatzeko, baina ez dute frogatzen grafo bat laua denik. Bi teoremek huts egiten badute, beste metodo batzuk erabili behar dira.