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, m^*(G - Y) = m^*(G) - m(〈Y^* 〉), 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, and so may simply be called "the" dual graph. Also, a graph is planar iff it has a combinatorial dual.

dual graph | geometric dual graph | planar graph