Let G be a connected graph. An algebraic dual of G is a graph G★ such that G and G★ have the same set of edges, any cycle of G is a cut of G★, and any cut of G is a cycle of G★. Every planar graph has an algebraic dual, which is in general not unique (any dual defined by a plane embedding will do). The converse is actually true, as settled by Whitney:
- A connected graph G is planar if and only if it has an algebraic dual.
The same fact can be expressed in the theory of matroids: if M is the graphic matroid of a graph G, then the dual matroid of M is a graphic matroid if and only if G is planar. If G is planar, the dual matroid is the graphic matroid of the dual graph of G.
Read more about this topic: Dual Graph
Famous quotes containing the words algebraic and/or dual:
“I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
—Henry David Thoreau (1817–1862)
“Thee for my recitative,
Thee in the driving storm even as now, the snow, the winter-day
declining,
Thee in thy panoply, thy measur’d dual throbbing and thy beat
convulsive,
Thy black cylindric body, golden brass and silvery steel,”
—Walt Whitman (1819–1892)