Subliminal Graph Duals

Gödel’s Lost Letter and P=NP 2020-02-02

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 ${V - E + F = 2}$ 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 ${G^*}$ need not be unique up to isomorphism—it may depend on how the original graph ${G}$ 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 ${G^*}$ of a graph ${G}$ drawn in the plane are:

Place a vertex for each face, including the region outside the graph.
For every edge in ${G}$ , add an edge to ${G^*}$ between the vertices of the adjoining faces.
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 ${G^*}$ , its dual is again the triangle graph. The property ${(G^*)^* = G}$ breaks down, however, for the tree and forest at right. All trees or forests of ${m}$ edges becomes a single node with ${m}$ loops. Moreover, the dual of the graph of ${m}$ 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 ${m}$ nodes, but if all ${m}$ loops are separate petals then the dual is the star of ${m}$ nodes. No disconnected graph can be a planar dual.

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

If ${G}$ is 3-connected, meaning that every pair of nodes ${u,v}$ can be connected by three paths that meet only at ${u}$ and ${v}$ , then all drawings of ${G}$ give the same ${G^*}$ and ${(G^*)^* = G}$ does hold. This was one of Whitney’s seminal results in the 1930s, and he proved this equivalent to ${G}$ being the skeleton of a convex polyhedron. 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 ${G}$ is planar if and only if there is a 1-1 map of its edges to edges of a graph ${G'}$ such that every cycle in ${G}$ maps to a minimal cut-set of ${G'}$ (i.e., a minimal set of edges whose removal disconnects ${G'}$ ) and vice-versa. Any dual of ${G}$ can be ${G'}$ . 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 ${K_5}$ or ${K_{3,3}}$ 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 ${G}$ 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 ${E}$ together with an integer function ${f}$ defined on subsets of ${E}$ such that:

${f(\emptyset) = 0}$ ;
for all ${a \in E}$ , ${f(\{a\}) \leq 1}$ ;
if ${A \subseteq B}$ then ${f(A) \leq f(B)}$ ; and
if ${A \subseteq B}$ and ${c \notin B}$ then ${f(B \cup \{c\}) - f(B) \leq f(A \cup \{c\}) - f(A)}$ .

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

$\displaystyle f_G(A) = \text{the maximum cardinality of a tree or forest using edges in }A.$

One attraction of matroids ${(E,f)}$ is that they automatically have duals ${(E,f^*)}$ where

$\displaystyle f^*(A) = |A| - f(E) + f(E \setminus A).$

Call ${(E,f)}$ a graphic matroid if there is a graph ${G = (V,E)}$ such that ${f = f_G}$ . What Whitney proved is:

Theorem 1 A graph ${G = (V,E)}$ is planar if and only if both ${(E,f_G)}$ and ${(E,f_G^*)}$ are graphic.

This is a beautiful statement. But it does not help us with isomorphism invariance. The trouble is that ${f_G}$ does not characterize ${G}$ . All trees ${G}$ have the same trivial ${f_G}$ where ${f_G(A)}$ is just the cardinality of ${A}$ . 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 ${1}$ .

Polymatroid Duality

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

$\displaystyle D[f](A) = c|A| - f(E) + f(E \setminus A),$

where ${c}$ can be any number. Note that provided ${f(\emptyset) = 0}$ ,

$\displaystyle \begin{array}{rcl} D^2[f](A) &=& c|A| - D[f](E) + D[f](E \setminus A) \\ &=& c|A| - c|E| - f(E \setminus E) + f(E) + c|E \setminus A| + f(E \setminus (E \setminus A)) - f(E)\\ &=& c|A| + c|E \setminus A| - c|E| + f(A) - f(E) - f(\emptyset) + f(E)\\ &=& f(A). \end{array}$

Thus ${D}$ is a duality operator regardless of what ${f}$ is, just so long as ${f(\emptyset) = 0}$ , and it doesn’t matter what ${c}$ is. Once ${c}$ is fixed we can write ${D[f] = f^*}$ , and then ${f^{**} = f}$ is guaranteed.

If we relax the second matroid axiom to read ${f(\{a\}) \leq k}$ for any ${a \in E}$ , then it is natural to take ${c = k}$ . This defines at a stroke both the notion of a ${k}$ -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 ${1}$ . And with ${k = 2}$ , graphs give us an example that is even simpler than the matroid ${(E,f_G)}$ . Define the rank function ${r_G}$ of a graph ${G = (V,E)}$ as the map from subsets ${A}$ of ${E}$ to

$\displaystyle r_G(A) = \text{the number of nodes touched by edges in } A.$

Then ${(E,r_G)}$ is a 2-polymatroid. A loop has rank ${1}$ but a regular edge has rank ${2}$ . The fourth axiom holds because if ${A \subseteq B}$ and an edge ${c}$ touches nodes ${u}$ and/or ${v}$ that no edge in ${B}$ touches, then no edge in ${A}$ touches them either.

Definition 2 A 2-polymatroid ${(E,f)}$ is graphic if there is a graph ${G = (V,E)}$ such that ${f = r_G}$ .

The first key fact is that ${r_G}$ is an isomorphism invariant of ${G}$ . The second is that ${r_G^{**} = r_G}$ , of course. So what does the dual ${(E,r^*_G)}$ 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 ${m}$ disjoint edges is a collection of ${m}$ 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 ${K_4}$ at right? It is after all planar. Consider any subset ${A}$ of one or two edges. The edge set ${E \setminus A}$ still spans the graph, so the ${r_G(E \setminus A) - r_G(E)}$ part of ${r^*_G}$ cancels, leaving ${r^*_G(A) = 2|A|}$ . 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 ${m}$ disjoint edges, but we already know that is the dual of ${m}$ circles, which is different. Hence the conclusion is:

The 2-polymatroid dual ${K^*_4}$ of ${K_4}$ 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 ${G_0}$ we are given.

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

Transform ${G_0}$ to its dual ${G_0^*}$ .
Perform an operation ${op}$ on ${G_0^*}$ to get ${G_1^*}$ .
Transform back to get ${G_1}$ .
Use ${G_1}$ and the simple nature of ${op}$ on the dual to infer something about ${G_0}$ .

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 ${e}$ . The deletion of an element ${e}$ from a polymatroid is well-defined: it is just the restriction to the subsets that didn’t include ${e}$ .

Theorem 3 For any graph ${G}$ and edge ${e}$ , ${(G^* \setminus e)^*}$ is a graph and is obtained by:

deleting ${e}$ and its incident node or nodes;

making any loop incident to ${e}$ or copy of ${e}$ into a circle; and

coiling back every other edge incident to ${e}$ 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 ${a}$ and ${b}$ changing roles. If we delete the edge ${a}$ from the dual we get a loop, which remains a loop on transforming back. That is the same as exploding ${a}$ in the lollipop: the “stick” part ${b}$ recoils into a loop. If instead we delete ${b}$ 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?

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.