grafo planare

Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano. Ad esempio sono planari i seguenti grafi: Il secondo può essere raffigurato senza archi che si intersecano spostando uno degli archi dati da una diagonale al di fuori del perimetro del quadrato. Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di archi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari: K5 K3,3 Si tratta del grafo completo con 5 nodi e del grafo bipartito completo con 3+3 nodi ; questi due grafi sono chiamati anche grafi di Kuratowski, in onore del matematico polacco Kazimierz Kuratowski. Si constata infatti che non è possibile ridisegnare queste raffigurazioni evitando che gli archi si intersechino. In effetti Kuratowski nel 1929 ha dimostrato che questi sono i due grafi non planari più ridotti, con il seguente enunciato.