Grafo dual

${\displaystyle G\leftrightarrow G''}$

${\displaystyle G}$

${\displaystyle G'}$

${\displaystyle G}$

En efecto, podemos representar ${\displaystyle G'}$ poniendo el vértice ${\displaystyle v_{f}'}$ de ${\displaystyle G'}$ dentro de la correspondiente cara ${\displaystyle f}$ de ${\displaystyle G}$ y dibujando una arista ${\displaystyle e'}$ de ${\displaystyle G'}$ que se corresponda con una arista ${\displaystyle e}$ de ${\displaystyle G}$ de forma que interseque a ${\displaystyle e}$ exactamente una vez y que no interseque ninguna otra arista de ${\displaystyle G}$ (ver dibujos de la derecha). Podemos ahora utilizar el teorema de la curva de Jordan para acabar de demostrar la anterior afirmación.

Esto nos da una biyección entre vértices de ${\displaystyle G}$ y caras de ${\displaystyle G'}$. Ahora, dada una cara de ${\displaystyle G'}$, esta está representada por un único vértice de ${\displaystyle G''}$ por definición. Esto nos da una biyección entre ${\displaystyle G'}$ y ${\displaystyle G''}$. Componiendo ambas biyecciones tenemos una biyección ${\displaystyle G\leftrightarrow G''}$.

Veamos que esta biyección conserva la adyacencia. Dos vértices ${\displaystyle u,v}$ de ${\displaystyle G}$ son vecinos en ${\displaystyle G}$ si y sólo si sus caras correspondientes ${\displaystyle f_{u}',f_{v}'}$ de ${\displaystyle G'}$ son contiguas. Equivalentemente, los vértices ${\displaystyle u'',v''}$ de ${\displaystyle G''}$ correspondientes a las caras ${\displaystyle f_{u}',f_{v}'}$ de ${\displaystyle G'}$ son vecinos. Por tanto, la adyacencia se conserva y tenemos pues un isomorfismo, como queríamos. ${\displaystyle \quad \square }$

${\displaystyle G'}$

${\displaystyle G'}$

${\displaystyle G}$

Como ${\displaystyle G'}$ no es bipartito, debe tener un ciclo de orden impar, pues si no lo tuviera sería bipartito. Consideremos ahora la representación de ese ciclo de orden impar. Una de las caras en su interior debe tener un número impar de aristas, pues si no el ciclo sería de orden par. Esa cara será un vértice de grado impar del grafo ${\displaystyle G''}$, por lo que ${\displaystyle G''}$ no es euleriano.

Pero, por la propiedad anterior, ${\displaystyle G''}$ es isomorfo a ${\displaystyle G}$, por lo que ${\displaystyle G}$ tampoco es euleriano, lo que es una contradicción. ${\displaystyle \quad \square }$