Graph Duality

Duality §

• Given a plane drawing of a planar graph , the dual graph is obtained as follows:

  1. For each face of choose a point
  2. For each edge , draw a line that crosses edge and no other edge, and joint the vertices in the faces that the edge bounds.

• Informally, a dual graph is a graph that shows whether two faces are touching each other

• A graph is an algebraic dual of if there is a bijection such that if the set forms a cycle in , then the corresponding set of edges forms a cut in .

  This extends the notion of the dual graph. We assert that the bijection exists rather than say any arbitrary cycle is the dual of any arbitrary cut-set

Cycle and Cut-set §

• The cut-set rank is the number of edges in a spanning forest of a graph . If is a graph with vertices and components, we have the cut-set rank as

• The cycle rank of an undirected graph is the total number of edges needed to be removed so that the resulting graph is a forest. If the graph has vertices, edges and components, we have

• Let be an edge of a spanning forest. The fundamental cut-set with respect to is the cut-set of which contains as well as the edges

  Where and are disconnected subgraphs that are produced when removing . The set of fundamental cut-sets is the fundamental set of cut-sets

• Let such that . Let be the unique -path from to on . The fundamental cycle is formed by the addition .

• (Wilson 15.3) Cycle Cut-Set Duality. Let be a planar graph and its dual. Then, a set of edges in forms a cycle in if and only if the corresponding edges in forms a cut-set.

• (Wilson 9.3a cor) Let be the fundamental set of cut-sets of associated with spanning forest . We have that

• (Wilson e5.12a) If is a cycle and is a cut-set of a connected graph , then then and have an even number of edges in common.

  • Proof: This is trivially true if and are edge disjoint.

    Since is a cut-set, it must disconnect the graph. Consider any two vertices . If they were separated because of the cut, then . But also, note that since is a cycle, some other -path that does not pass through must exist and be deleted

    This applies if we consider any pair of vertices as listed in the cycle. Hence, there is always an even number of edges that are both in the cycle and in the cut-set.

• (Wilson e5.12b) If is any set of edges in with an even number of edges in common with each cut-set of , then can be split into edge-disjoint cycles

  • Proof Let be the union of

    We prove by contradiction Also, without loss of generality we assume is connected otherwise we apply the same logic here to each component of .

    cannot be split into edge disjoint cycles. This implies that there is at least one edge that appears in two cycles say and . Say the set of edges they have in common is and

    Now for any cut-set that does not cut these common edges, by Wilson e5.12a, there must be an even number of edges shared by the cycles with which means there are a total of edges shared by , and this quantity must be even by our stipulations. Furthermore, by Wilson e5.11a there must exist a cycle which does not pass through any edge in and clearly it intersects with in edges

    But, now consider a cut-set obtained by passing through one of the edges in which is guaranteed to exist by Wilson e5.11b. Such a cut-set now yields common edges with which is impossible since there must be an even number of edges shared between and .

• A linear algebra-based interpretation for cut-sets and cycles is provided here

Vertex and Face §

• (Wilson 19.2) Let be a Plane Graph without loops and be the dual graph. Then, is -colorable if and only if is -face colorable.
• (Wilson 15.1) In the dual graph, we have that
  Where denote the number of vertices, edges and faces
• (Wilsson 15.2) - If is a connected planar graph, then
• (Wilson 15.5) If is an algebraic dual of , then is an algebraic dual of

Links §

• Introduction To Graph Theory by Wilson

• Trails, Walks, Paths and Cycles

• Graph Planarity

• Trees

• Matroid Theory