Teorema de Wagner

Otro resultado también conocido a veces como teorema de Wagner establece que un grafo 4-vértices-conectadp es plano si y solo si no tiene K5 como menor.

Es decir, al asumir un mayor nivel de conectividad, se puede hacer innecesario el grafo K3,3 en la caracterización, quedando solo un único menor prohibido, K5.

Correspondientemente, la conjetura de Kelmans-Seymour establece que un grafo 5-conectado es plano si y solo si no tiene K5 como menor.

[3]​ Una consecuencia de la versión más fuerte del teorema de Wagner para grafos cuatriconexos es caracterizar los grafos que no tienen a K5 como menor.

[5]​ Los análogos del teorema de Wagner también se pueden extender a la teoría de los matroides: en particular, los mismos dos grafos K5 y K3,3 (junto con otras tres configuraciones prohibidas) aparecen en una caracterización de los matroides gráficos por menores matroides prohibidos.

K 5 (izquierda) y K 3,3 (derecha) como menores del grafo de Petersen no plano (pequeños círculos de colores y bordes negros sólidos). Los menores se pueden formar eliminando el vértice rojo y contrayendo los bordes dentro de cada círculo amarillo.
Una suma de cliques de dos grafos planos y el grafo de Wagner, formando un grafo libre de K 5
Existe una demostración sin palabras de que un grafo hipercúbico es no-plano usando el teorema de Kuratowski o el teorema de Wagner; para encontrar los subgrafos K 5 (arriba) o bien K 3,3 (abajo)