Grafo de ápice

El vértice eliminado se llama ápice del grafo.[4]​ Los grafos de ápice son cerrados bajo la operación de tomar menores: contraer cualquier arista, o eliminar cualquier arista o vértice, conduce a otro grafo apical.Porque, si G es un grafo de vértice con ápice v, entonces cualquier contracción o eliminación que no involucre a v conserva la planitud del grafo restante, al igual que cualquier eliminación de una arista que incida en v.Si se contrae una arista incidente en v, el efecto sobre el grafo restante es equivalente a la eliminación del otro extremo de la arista.De manera más general, para cualquier k constante fija, es posible reconocer en tiempo lineal los grafos k-apicales, los grafos en los que la eliminación de un conjunto cuidadosamente elegido de como máximo k vértices conduce a un grafo plano.[9]​ Sin embargo, si es falsa, solo tiene un número finito de contraejemplos.Para comprobarlo, simplemente basta agregar el número de puentes al empotramiento plano, conectando entre sí todas las caras en las que se debe enlazar v.[16]​ Los grafos de vértice también son embebibles sin enlaces en el espacio tridimensional: se pueden incrustar de tal manera que cada ciclo del grafo sea el límite de un disco que no está atravesado por ningún otro elemento del grafo.Dado que cada grafo de ápice se puede incorporar sin enlaces, esto muestra que hay grafos que se pueden incorporar sin enlaces pero no reducibles con YΔY y, por lo tanto, hay menores prohibidos adicionales para los grafos reducibles con YΔY.Por ejemplo, en los grafos no planos de menor-mínimo K5 y K3,3, cualquiera de los vértices se puede elegir como vértice.Wagner (1970) definió un grafo casi plano como un grafo de ápice no plano con la propiedad de que todos los vértices pueden ser ápices del grafo; por lo tanto, K5 y K3,3 son casi planos.Antes de la prueba del teorema de los cuatro colores, se demostró que cada grafo casi plano se puede colorear con un máximo de cuatro colores, a excepción de los grafos formados a partir de un grafo rueda con un ciclo externo impar al reemplazar el vértice central con dos vértices adyacentes, lo que requiere cinco colores.Además, demostró que, con una sola excepción (el grafo complemento de ocho vértices del cubo), cada grafo casi plano tiene una incrustación en el plano proyectivo.