El teorema de Kuratowski dice que..:
un gráfico finito es plano si y sólo si no contiene un subgrafo que es una subdivisión de $K_5$ (el gráfico completo en cinco vértices) o de $K_{3,3}$ (gráfico bipartito completo en seis vértices, tres de los cuales se conectan a cada uno de los otros tres, también conocido como gráfico de utilidad). Si $G$ es un gráfico que contiene un subgrafo $H$ que es una subdivisión de $K_5$ o $K_{3,3}$ Entonces $H$ se conoce como Kuratowski subgrafo de $G$ . Con esta notación, el teorema de Kuratowski puede ser expresado sucintamente:
un gráfico es plano si y sólo si no tiene un subgrafo de Kuratowski.
Si es así, lo hemos hecho:
1) "si no es plano y sin subgrafo, entonces 3-conectado".
2) "si 3-conectado y sin subgrafo, entonces plano".
Por lo tanto, la "forma lógica" de 1) es:
$( \lnot PL \land NS) \to 3C$
mientras que para el 2) lo hemos hecho:
$(3C \land NS) \to PL$ .
Mientras que el teorema de Kuratowski equivale a:
$PL \leftrightarrow NS$ ,
donde $NS$ representa: "el gráfico no tiene un subgrafo de Kuratowski".
Podemos probar que 1) y 2) implican $NS \to PL$ :
1) $( \lnot PL \land NS) \to 3C$ --- premisa
2) $(3C \land NS) \to PL$ --- premisa
3) $ \lnot PL$ --- asumió [a]
4) $NS$ --- asumido [b]
5) $3C$ --- de 3) y 4) por $ \land $ -intro y $ \to $ -eliminar con 1)
6) $PL$ --- de 4) y 5) por $ \land $ -intro y $ \to $ -eliminar con 2)
7) contradicción --- de 3) y 6)
8) $PL$ --- de 3) y 7) por Doble negación , descargando [a]
9) $NS \to PL$ --- de 4) y 8) por $ \to $ -intro, descargando [b].
Pero la otra "dirección": $PL \to NS$ no está implícito en los puntos 1) y 2).
Considere el caso cuando $PL$ es Verdadero y $NS$ es Falso tenemos que 1) es verdadero [ $(F \land F) \to ?$ es Verdadero y también 2) es Verdadero [a condicional con verdadero cosequente es siempre Verdadero ], mientras que $PL \to NS$ es Falso [ $T \to F$ es Falso ].
