Combinatorial Dual Graph

Let m(G) be the cycle rank of a graph G, m^*(G) be the cocycle rank, and the relative complement G-H of a subgraph H of G be defined as that subgraph obtained by deleting the lines of H. Then a graph G^* is a combinatorial dual of G if there is a one-to-one correspondence between their sets of lines such that for any choice Y and Y^* of corresponding subsets of lines,


where <Y^*> is the subgraph of G^* with the line set Y^*.

Whitney showed that the geometric dual graph and combinatorial dual graph are equivalent (Harary 1994, p. 115), and so may simply be called "the" dual graph. Also, a graph is planar iff it has a combinatorial dual (Harary 1994, p. 115).

See also

Dual Graph, Geometric Dual Graph, Planar Graph

Explore with Wolfram|Alpha


Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 113-115, 1994.

Referenced on Wolfram|Alpha

Combinatorial Dual Graph

Cite this as:

Weisstein, Eric W. "Combinatorial Dual Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications