Let be the cycle rank of a graph , be the cocycle rank, and the relative complement of a subgraph of be defined as that subgraph obtained by deleting the lines of . Then a graph is a combinatorial dual of if there is a one-to-one correspondence between their sets of lines such that for any choice and of corresponding subsets of lines,
where is the subgraph of with the line set .
Whitney (1932) showed that the geometric dual graph and combinatorial dual graph are equivalent for planar graphs (Fleischner 1973; 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).