TOPICS

# Combinatorial Dual Graph

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).

Dual Graph, Geometric Dual Graph, Planar Graph

## Explore with Wolfram|Alpha

More things to try:

## References

Fleischner, H. "The Uniquely Embeddable Planar Graphs." Disc. Math. 4, 347-358, 1973.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 113-115, 1994.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

## Referenced on Wolfram|Alpha

Combinatorial Dual Graph

## Cite this as:

Weisstein, Eric W. "Combinatorial Dual Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/CombinatorialDualGraph.html