Question

(i) Give an example to show that, if \(G\) is a disconnected plane graph, then \(G^{* *}\) is not isomorphic to \(G\). (ii) Prove the result of part (i) in general.

Short answer

Step by step, we have given an example of a disconnected plane graph \(G\) along with the calculation of its dual graph \(G^{*}\) and the final computation of its double dual \(G^{**}\). After the comparison between \(G\) and \(G^{**}\), we have confirmed that they are not isomorphic. Then, we generalized the proof for any disconnected graph \(G\), and similarly showed that \(G^{**}\) is not isomorphic to \(G\).

Step-by-step solution

Example of a disconnected plane graph

Begin with a simple disconnected plane graph \(G\), such as two separate vertices. The graph \(G\) has 2 vertices with no edges connecting them.

Compute the dual \(G^{*}\) of the plane graph \(G\)

The dual of a plane graph is obtained by placing a vertex in each face of the graph, and connecting two vertices if their corresponding faces share an edge in the original graph. However, since \(G\) is disconnected, it has only one face, hence the dual \(G^{*}\) will consist of a single isolated vertex, with no edges.

Compute the double-dual \(G^{**}\)

Now compute the dual of \(G^{*}\). As \(G^{*}\) is a single isolated vertex, its dual will also be a single isolated vertex, which means \(G^{**}\) is a single isolated vertex.

Compare \(G\) and \(G^{**}\)

Finally, comparing the original graph \(G\) to its double-dual \(G^{**}\), it can be seen that they are not isomorphic, because \(G\) contains two vertices while \(G^{**}\) contains a single vertex.

Prove the result in general.

To prove this in general, consider any disconnected plane graph \(G\). Then, consider the dual graph \(G^{*}\), and then the dual of this graph to obtain \(G^{**}\). It's clear that for any disconnected plane graph, \(G^{*}\) is also disconnected, hence \(G^{**}\) is not isomorphic to \(G\). This is because the vertices of \(G^{*}\) correspond to the faces of \(G\), and the vertices of \(G^{**}\) correspond to the faces of \(G^{*}\), and the faces of \(G\) and \(G^{*}\) are not connected in the same way. Therefore, for any disconnected plane graph \(G\), \(G^{**}\) is not isomorphic to \(G\).

Key concepts

Graph Theory Essentials

Graph theory is a foundational area of mathematics that deals with the study of graphs, which are structures made up of vertices (also called nodes) and edges that connect these vertices. It's a powerful tool not only in mathematics but also in computer science, biology, and social science due to its ability to represent complex relationships and networks efficiently.

In the context of graph theory, an isomorphism between two graphs signifies a mapping between the vertices of one graph to another that preserves the edge-vertex connectivity. Essentially, if two graphs are isomorphic, one can be transformed into the other simply by renaming the vertices. This is akin to having two different blueprints for the same house – they may look different at first glance, but all the rooms (vertices) and doors (edges) match one to one. The study of plane graphs, those drawn on a plane with no edges crossing, introduces unique considerations, such as the concept of faces, or regions bounded by edges.

An essential aspect for students to grasp is that isomorphic graphs are considered the 'same' in graph theory because their structural properties and therefore the problems they model are identical, despite possible differences in representation.

The Dual Graph Connection

Within graph theory, the concept of a dual graph, denoted by the symbol * or ^*, is particularly intriguing when dealing with plane graphs. For a given plane graph G, its dual graph G^* is constructed so that for every face in G, there is a corresponding vertex in G^*, and for every edge in G shared by two faces, there is an edge in G^* connecting the corresponding vertices.

Understanding dual graphs requires envisioning each face of the original graph as a distinct area of interest. Suppose you had a map with countries (faces of G); the dual graph would create a new 'capital city' (vertex of G^*) within each country, connecting these capitals with 'diplomatic routes' (edges of G^*) wherever the countries shared a border. However, for disconnected graphs - graphs that have parts not reachable from other parts - the dual graph must represent these standalone elements appropriately, which often leads to a change in the properties of the graph, such as the number of components and is an essential notion when considering graph isomorphism.

Understanding Disconnected Graphs

A disconnected graph is analogous to an archipelago - each group of related vertices (an island) is isolated from the rest. When examining a disconnected plane graph, it's crucial to recognize that, unlike connected graphs, there are unreachable vertices from any given vertex, indicating separate components in the graph. In the realm of graph theory, each of these components is treated as an independent graph.

A powerful demonstration of the unique properties of disconnected graphs comes from exploring their duals. As elucidated in the textbook solution, a disconnected graph G produces a dual graph G^* that significantly alters connectivity. In such cases, analyzing the double-dual G^** further elucidates the intricate shifts in structure, emphasizing that the isomorphism does not necessarily hold for disconnected graphs. Hence, for students, it is vital to understand that the exercise of computing dual and double-dual graphs not only serves to deepen understanding of plane graphs but also to unravel the effects of graph connectivity on isomorphism.