Un vértice no etiquetado es uno que puede ser sustituido por cualquier otro vértice basado sólo en sus adyacencias en el grafo, y no en información adicional a éste.