thumb|300px|El grafo G es dual del G', y viceversa.
En teoría de grafos, un grafo dual G' de un grafo planar G es un grafo que tiene un vértice por cada región de G, y una arista por cada arista en G uniendo a dos regiones vecinas.
Propiedades 300px|thumb|G' y G″ son duales de G, pero no isomorfos. Si G' es el grafo dual de un grafo planar G, entonces G' también es un grafo planar (que puede tener bucles y ser un multigrafo, es decir, tener aristas múltiples). Si G es un grafo planar, entonces puede que no exista un único grafo dual para G, en el sentido que G puede tener grafos duales no-isomorfos, dependiendo de la distribución particular de los planos. En la figura, G′ y G″ no son isomorfos porque G′ tiene un nodo con grado 6 (la región exterior) que G″ no tiene (ver diagrama). Una propiedad muy importante es la siguiente:
Un grafo es isomorfo al dual de su dual, que denotaremos por .
Esto permite demostrar otras propiedades como, por ejemplo,
Si un grafo planar es euleriano, su grafo dual es bipartito.
Grafo autodual
Un grafo autodual es aquel que es isomorfo a su dual.
Propiedades
Sean dos grafos planares G=(V,E) y G'=(V',E'), cuyos conjuntos de regiones son R y R' , respectivamente, entonces: |E'| = |E| |V'| = |R| |R'| = |V|
Referencias
H. Whitney, Non-separable and planar graphs, Trans. Amer. Math. Soc. 34 (1932), 339–362.
Dual Categoría:Teorías de dualidad Categoría:Grafos planares Categoría:Teoría de grafos topológicos de:Dualität (Mathematik)#Geometrisch dualer Graph