spezieller Graph der folgenden Art. Der duale Graph eines zusammenhängenden Graphen oder Pseudographen G₁ ist ein zusammenhängender Graph oder Pseudograph G₂, für den eine Bijektion φ : K(G₁) → K(G₂) zwischen den beiden Kantenmengen existiert so, daß K′ ⊆ K(G₁) genau dann die Kantenmenge eines Kreises von G₁ ist, wenn G₂ − φ(K′) nicht mehr zusammenhängend ist, wohl aber G₂ − K″ für alle echten Teilmengen K″ von φ(K′).

Ein Graph besitzt genau dann einen dualen (Pseudo-) Graphen, wenn er ein planarer Graph ist. Für einen ebenen Graphen G läßt sich ein dualer (Pseudo-) Graph G′ leicht folgendermaßen konstruieren:

Zunächst plaziert man in jedem Land (ebener Graph) von G genau eine der Ecken von G′. Sind zwei Länder von G benachbart und ihre Ränder enthalten l gemeinsame Kanten, dann verbindet man die beiden in ihnen liegenden Ecken in G′ mit l Kanten, die jeweils eine der Kanten zwischen den beiden Ländern, aber keine weitere Kante von G schneiden. Der so definierte duale (Pseudo-) Graph ist ebenfalls eben.

Bei der Untersuchung von Färbungen von Landkarten ist die Betrachtung dualer Graphen oft nützlich, denn die Landkarte eines ebenen Graphen besitzt genau dann eine Färbung mit k Farben, wenn ihr dualer Graph eine Eckenfärbung mit k Farben besitzt.

Es gilt folgende Aussage: Der duale (Pseudo-) Graph eines dreifach zusammenhängenden Graphen ist eindeutig bestimmt, enthält weder Schlingen noch parallele Kanten, und ist selbst wieder dreifach zusammenhängend.