Question

(i) Give an example to show that, if \(G\) is a connected plane graph, then any spanning tree in \(G\) corresponds to the complement of a spanning tree in \(G^{*}\). (ii) Prove the result of part (i) in general. (This result will also be needed in Chapter 7.)

Short answer

An example of a connected plane graph is a triangle, and for this case a spanning tree in \(G\) corresponds to the complement of a spanning tree in its dual \(G^*\). The general case can be proven by considering the boundary relationship between edges not in the spanning tree of \(G\) and faces in \(G\), which gives rise to vertices and edges in \(G^*\). Therefore, for every graph \(G\), a spanning tree in \(G\) corresponds to the complement of a spanning tree in \(G^*\).

Step-by-step solution

Understanding the Basics

A connected plane graph is a graph that is drawn in the plane without any edge crossings, and is connected, meaning there is a path from any one vertex to any other vertex. A spanning tree of this connected plane graph is a subgraph that is a tree which includes all of that graph's vertices with the minimal possible number of edges. A dual graph \(G^*\) of a plane graph \(G\) is obtained by placing a vertex in each region of \(G\) and connecting two vertices with an edge if and only if their corresponding regions in \(G\) are adjacent.

Constructing the Example

Consider a triangle in graph \(G\), whose corresponding spanning tree consists of two edges, leaving out one edge. Its dual graph \(G^*\) will be a single vertex, whose corresponding tree consists of zero edges and one vertex. Here, the sum of the edges in both spanning trees in graph \(G\) and its dual \(G^*\) equals to the total number of edges in \(G\). Each edge not in the spanning tree of \(G\) corresponds to an edge in the spanning tree of \(G^*\), and vice versa. In other words, the spanning tree of \(G\) corresponds to the complement of the dual graph \(G^*\).

Proving the Result in General

Considering any edge e of \(G\) not in the spanning tree of \(G\), and the face f of \(G\) which e bounds. Since f gives rise to a vertex of \(G^*\) and e gives rise to an edge of \(G^*\) incident to the vertex coming from f, if e does not belong to the spanning tree of \(G\), then its dual will belong to the spanning tree of \(G^*\). Conversely, if e belongs to the spanning tree of \(G\), then the dual of e will not belong to the spanning tree of \(G^*\). Therefore, for every graph \(G\), a spanning tree in \(G\) corresponds to the complement of a spanning tree in its dual \(G^*\).

Key concepts

Spanning Tree

In graph theory, a 'spanning tree' is a fundamental concept. Imagine you have a network that connects various points, known as vertices, and you need to touch all those points using the least number of connections possible. This is what a spanning tree achieves. It is a subgraph that connects all the vertices of the original graph with the minimum number of edges.

Important characteristics of a spanning tree are:

• It includes all the vertices of the original graph.
• It has exactly \( n - 1 \) edges, where \( n \) represents the number of vertices.
• It contains no cycles, which means there is precisely one path between any two vertices.

Think of a spanning tree as a simplified version of the graph that retains connectivity but removes any redundant connections. This characteristic plays a key role in various network design tasks, such as laying out cables or circuits with a minimal cost.

Dual Graph

A dual graph is a concept that's quite intriguing when dealing with plane graphs. If you have a graph \( G \) that is drawn without any edges crossing, you can create its dual graph \( G^* \). The process involves placing a vertex in each region of \( G \).

Here's how a dual graph is constructed:

• Each face or region of the original graph becomes a vertex in the dual graph.
• An edge exists between two vertices in the dual graph if their corresponding regions in the original graph are adjacent (meaning they share a boundary).

This relationship means that actions in the original graph can be mirrored or responded to in the dual. The dual graph can help to analyze and solve various problems related to connectivity and flow within networks. For instance, understanding and analyzing electric networks or geographical maps can often use duality principles.

Connected Graph

A connected graph is essential in understanding how graphs work. For a graph to be connected, there must be a path between every pair of vertices. This means no vertex is isolated from another.

Key points about connected graphs:

• Every vertex is reachable from any other vertex.
• There are no separate parts or components, the entire graph is one big component.

A connected graph ensures that whatever network you are analyzing—whether it be a computer network, a social network, or a public transportation map—any point can reach any other point. This is crucial for efficient design and operation because disconnections could mean the failure of a network or the inability to communicate or travel to certain parts.

Complement in Graph Theory

A graph's complement might sound like a puzzle, but it's quite straightforward. Simply put, the complement of a graph \( G \) is a graph that has the same vertices as \( G \) but includes every edge that \( G \) does not.

To visualize a complement graph:

• Consider all possible edges that could exist between the vertices.
• Include in the complement only those edges that are missing in the original graph.

This concept is particularly useful in understanding the absence of certain connections and their implications for the overall structure of the graph. When looking for a spanning tree in a graph, its complement graph provides insights into the edges that are left out and could be relevant in other network studies or optimizations.