Given a planar graph with a particular planar embedding, a geometric dual graph and combinatorial dual graph can be defined. Whitney (1932) showed that these are equivalent for planar graphs (Fleischner 1973, Harary 1994. p. 115) so that one may speak of "the" dual graph . The illustration above shows the process of constructing a geometric dual graph from a planar nonpolyhedral graph, leading to a multigraph.
While some nonpolyhedral planar graphs have a unique dual, a general planar graph has multiple dual graphs depending on the choice of planar embedding. A planar graph has a unique embedding (and hence is said to be unqiuely embeddable), and consequently a unique dual, iff it is a graph subdivision of a polyhedral graph. The complete bipartite graph is an example of a planar nonpolyhedral graph whose embeddings are all isomorphic, meaning its dual graphs are also isomorphic and it is uniquely embeddable.
On the other hand, polyhedral graphs have unique dual graphs. The dual graph of a polyhedral graph has graph vertices each of which corresponds to a face of and each of whose faces corresponds to a graph vertex of . Two nodes in are connected by an graph edge if the corresponding faces in have a boundary graph edge in common. As a result, each edge of a graph has a corresponding dual edge in corresponding to the edge that connects the two faces on either side of , meaning the edge counts are the same. Combined with the switching of the roles of faces and vertices, this gives the relations
(1)
| |||
(2)
| |||
(3)
|
between dual and primal edge, face, and vertex counts. They also of course satisfy the polyhedral formula
(4)
| |||
(5)
|
The dual graph of a wheel graph is itself a wheel (Skiena 1990, p. 147). In general, a graph that is dual to itself is called a self-dual graph.
The notation of duality can be generalized to embeddings other than those in the plane and hence to nonplanar graphs. This is closely related to the concept of double covers.
Graph duals of named graphs are implemented in the Wolfram Language as GraphData[graph, "DualGraph"].
The Tutte polynomial of the dual graph of a graph is given by
(6)
|
i.e., by swapping the variables of the Tutte polynomial of the original graph.