Subliminal Graph Duals

Why don’t we have a good general notion of graph duality?

Nat. Medal of Science source

Hassler Whitney was an American mathematician. He contributed seminal ideas to both discrete and continuous mathematics and forged between the two. One of his early results was an algebraic characterization of duality in planar graphs that later led him to found matroid theory.

Today we discuss notions of duality for general graphs.

Duality in planar graphs goes back even before Leonhard Euler and his famous formula for the vertices, edges, and faces of a polyhedron. Johannes Kepler recognized that if one assigns a node to each face of the cube and connect the nodes of adjacent faces, then one obtains the skeleton of the octahedron. If one similarly makes a graph from the eight faces of the octahedron, then the skeleton of the cube reappears. Thus the cube and octahedron are dual to each other, as are the dodecahedron and the icosahedron. The tetrahedron is self-dual.

Still in the years before Euler began graph theory by abstracting the islands and bridges of Königsberg (now Kaliningrad, Russia), the idea of duality proved useful in engineering for diagramming stresses between struts in bridges and similar structures. This required going beyond polyhedra to consider planar graphs that might have multiple edges or even loops. This is the kind of duality that Whitney characterized. But there are two drawbacks:

• It only applies to planar graphs.

• The dual graph need not be unique up to isomorphism—it may depend on how the original graph is drawn.

We can embed graphs on surfaces of higher genus to answer the former objection, but then the second still bites and other properties break down. We are mindful of Michael Atiyah’s opening words in his 2007 essay, “Duality in Mathematics and Physics”:

Duality in mathematics is not a theorem, but a “principle.”

But graphs don’t even seem to fulfill the “principle” part. Let’s see why.

Planar Duality

The rules to build the dual of a graph drawn in the plane are:

1. Place a vertex for each face, including the region outside the graph.

2. For every edge in , add an edge to between the vertices of the adjoining faces.

3. If the adjoining faces are the same face, the vertex gets a loop.

Consider the triangle graph at left below. There is only an inside face and an outside face. By rule 3 we need to connect the corresponding vertices once for each edge. Thus we get three parallel edges.

Despite the multiplicity of , its dual is again the triangle graph. The property breaks down, however, for the tree and forest at right. All trees or forests of edges becomes a single node with loops. Moreover, the dual of the graph of loops at one node depends on how the graph is drawn. If there are at most two nested “petals” of loops then the dual is a path of nodes, but if all loops are separate petals then the dual is the star of nodes. No disconnected graph can be a planar dual.

The problem emerges even when and are both simple graphs—note how the dual’s maximum node degree equals the size of the outer face:

If is 3-connected, meaning that every pair of nodes can be connected by three paths that meet only at and , then all drawings of give the same and does hold. This was one of Whitney’s seminal results in the 1930s. The above graph and its duals are not 3-connected, as is most readily seen by noting that each becomes disconnected upon removing its two vertices in the central column as drawn.

Plane Speaking

Whitney also proved that a connected graph is planar if and only if there is a 1-1 map of its edges to edges of a graph such that every cycle in maps to a minimal cut-set of (i.e., a minimal set of edges whose removal disconnects ) and vice-versa. Any dual of can be . The point is that this duality condition makes no direct reference to the geometry of polyhedra or the sphere or plane. Unlike the famous theorem by Kazimierz Kuratowski that a graph is non-planar if and only if it has or as a minor, it seems not so easily extended to surfaces of higher genus.

You may wonder by now: why not just regard the complement of as the dual? This would be fine if we ruled out having loops or multiple edges. But the drift of the above is to include them. If so, how would we cap the multiplicity to define the complement?

One more theorem by Whitney points in a direction that embraces loops and multiple edges and more. A matroid can be defined as a set together with an integer function defined on subsets of such that:

1. ;

2. for all , ;

3. if then ; and

4. if and then .

The rank of (finite) sets of vectors in a vector space obeys these properties. The last property intuitively says that if is independent of then it is certainly independent of any subset of . The following function on sets of edges in a graph obeys these rules:

One attraction of matroids is that they automatically have duals where

Call a graphic matroid if there is a graph such that . What Whitney proved is:

Theorem 1 A graph is planar if and only if both and are graphic.

This is a beautiful statement. But it does not help us with isomorphism invariance. The trouble is that does not characterize . All trees have the same trivial where is just the cardinality of . The shape of the tree does not matter. Ditto forests. We can get on a better track, however, by loosening up the requirement that the rank of a single element is at most .

Polymatroid Duality

Let’s actually forget about the matroid axioms and just think about the following operator on any functions of subsets of :

where can be any number. Note that provided ,

Thus is a duality operator regardless of what is, just so long as , and it doesn’t matter what is. Once is fixed we can write , and then is guaranteed.

If we relax the second matroid axiom to read for any , then it is natural to take . This defines at a stroke both the notion of a -polymatroid and its dual. The “poly” in the name sounds scary but it just means that the rank of a single element can be more than . And with , graphs give us an example that is even simpler than the matroid . Define the rank function of a graph as the map from subsets of to

Then is a 2-polymatroid. A loop has rank but a regular edge has rank . The fourth axiom holds because if and an edge touches nodes and/or that no edge in touches, then no edge in touches them either.

Definition 2 A 2-polymatroid is graphic if there is a graph such that .

The first key fact is that is an isomorphism invariant of . The second is that , of course. So what does the dual look like? Here are the 2-polymatroid duals of the graphs consisting of one loop, one edge, and two edges:

The dual of the edge incident to two nodes is an edge incident to zero nodes, which is called a circle. The dual of a forest of disjoint edges is a collection of circles. The intuition is that the disjoint edges are maximally independent, like a basis of a vector space. The dual of a basis is the zero vector, and the circles are like copies of the zero vector. The path of two nodes at right is not maximally independent and its dual is a double-loop. The single loop is self-dual. Also self-dual are the “lollipop” graph, which consists of one edge and one loop, and the triangle graph:

What about the dual of at right? It is after all planar. Consider any subset of one or two edges. The edge set still spans the graph, so the part of cancels, leaving . Thus every pair of edges in the dual would have to be independent, hence disjoint. In a graph, this means we’d have to have disjoint edges, but we already know that is the dual of circles, which is different. Hence the conclusion is:

The 2-polymatroid dual of exists and is unique but is not a graph.

Indeed, every graph in which all nodes have degree 3 or more has a dual that “goes invisible” as far as graphs are concerned. Yet we will argue that those duals are still useful for studying graphs.

My Invisible Dual Friend

What are duals good for? We don’t often want to prove something about the dual. We want to prove something about the original we are given.

What we have in mind is the kind of proof that goes:

1. Transform to its dual .

2. Perform an operation on to get .

3. Transform back to get .

4. Use and the simple nature of on the dual to infer something about .

Thus we can still use the duals implicitly. The existence of the dual for all graphs and its uniqueness (well, up to isolated nodes—a topic for a next post) will help us here. We also need that the transformed-back object is always a graph again, of course.

Perhaps the simplest operations are adding or deleting an edge . The deletion of an element from a polymatroid is well-defined: it is just the restriction to the subsets that didn’t include .

Theorem 3 For any graph and edge , is a graph and is obtained by:

• deleting and its incident node or nodes;

• making any loop incident to or copy of into a circle; and

• coiling back every other edge incident to into a loop at its other node.

This is the operation we called “explosion” in two previous posts.

To check the theorem, note how the “lollipop” graph is self-dual but with the edges and changing roles. If we delete the edge from the dual we get a loop, which remains a loop on transforming back. That is the same as exploding in the lollipop: the “stick” part recoils into a loop. If instead we delete from the dual we are left with a regular edge, which transforms back into a circle. That is the same as what is left of the head of the lollipop upon exploding the stick. Here are two more examples of explosions:

What is this good for? We will say more in an upcoming post.

Open Problems

What is the best way of visualizing the 2-polymatroid duals of graphs when they aren’t graphs? Note that deleting an edge in a graph embedded in the plane or some other surface effects contraction of the corresponding edge in the dual graph. It is clean to see the contraction as merging the nodes of the two faces. Thus a means of visualizing the 2-polymatroid would have to clean up explosions nicely, but as the above drawings show they can be quite messy.

Should we accept an answer where most of the graph duals are submerged below the surface? In a paper by James Oxley and Geoff Whittle that we have referenced before, we take this remark—

One of the attractions of matroid theory is that it has a satisfactory theory of duality.

—as hinting there is no satisfactory answer otherwise.

[deleted one attribution to Whitney that should go to Ernst Steinitz: this; added remark about visualizing explosions]