Isomorfismo.

Las siguientes instrucciones se dan a dos personas que no pueden ver el papel de la otra: Dibuje y etiquete 5 vertices con las siguientes letras: a, b, c, d, e. Conecte a con b, b con c, c con d, d con e y e con a.

Las gráficas producidas se aprecian en las siguientes figuras, sin duda estas figuras definen la misma gráfica aún cuando parezcan diferentes, se dice que estas gráficas son isomorfas.

La gráfica G1 yG2 son isomorfas si existe una función d 1 a 1 y sobre de los vértices de G1 a los vértices de G2, de manera que una arista E es insidente en v y w en G1 si sólo si la arista G (E) es insidente en f(v) y f(w) en G2. El par de funciones de f y g reciben el nombre de isomorfismo de G1 y G2.

Tres ciudades C1, C2 y C3 deberan conectars en forma directa mediante autopistas como cada una de las otras 3 ciudades C4, C5 y C6. Puede diseñarse este sistema de carreteras de manera que la autopista no se crucen. La siguiente figura ilustra un sistema en el que las autopistas se cruzan.

Una gráfica es plana si se puede dibujar en el plan sin que sus aristas se crucen.

Al diseñar circuitos impresos es deseable tener el menor número de cruces posibles, así el diseñador de circuitos impresos se enfrenta con el problema de gráficas planas.

Si una gráfica plana conexa se dibuja en el plano, este se divide en regiones contiguas llamadas caras. Una cara se caracteriza por el ciclo que forma su frontera. Por ejemplo, en la siguiente gráfica, la cara a tiene como un límite el ciclo (5, 2, 3, 4, 6, 1) y en el límite de la cara c es el ciclo (1, 2, 5,1). La cara exterior d se considera limida  por el ciclo (1, 2, 3, 4, 6, 1) La gráfica de la figura tiene f= 4 caras, e= 8 aristas. v= 6 vertices.

Obserbe que f, e y v satisfacen la ecuación f =  e - v + 2.

En 1752 Euler provó que la ecuación se cumple para cualquier gráfica con hexapiana.