Question

A planar graph \(G\) is outerplanar if \(G\) can be drawn in the plane so that all of its vertices lie on the exterior boundary. (i) Show that \(K_{4}\) and \(K_{2,3}\) are not outerplanar. (ii) Deduce that, if \(G\) is an outerplanar graph, then \(G\) contains no subgraph homeomorphic or contractible to \(K_{4}\) or \(K_{23}\). (The converse result also holds, yielding a Kuratowski-type criterion for a graph to be outerplanar.)

Short answer

We found that it is not possible to draw \(K_{4}\) and \(K_{2,3}\) while keeping all vertices on the external boundary, hence they are not outerplanar. And from this we deduced the fact that if a graph \(G\) is outerplanar it contains no subgraph homeomorphic or contractible to \(K_{4}\) or \(K_{23}\).

Step-by-step solution

Reasoning about \(K_{4}\)

The complete graph \(K_{4}\) has 4 vertices and 6 edges. A graph is outerplanar if it can be drawn without crossing edges such that all vertices lie on the boundary of the exterior face. Attempt to draw \(K_{4}\) this way, and discover that no such arrangement exists. This is because a vertex should be placed inside the triangle formed by the other three vertices to connect it with the others without making any edge crossings, which contradicts the condition of being outerplanar.

Reasoning about \(K_{2,3}\)

The bipartite graph \(K_{2,3}\) has two sets of vertices, one with 2 vertices and the other with 3 vertices, and each vertex in one set is connected to every vertex in the other set. A bipartite graph is outerplanar if it can be drawn without crossing edges such that all vertices lie on the boundary of the exterior face. Now try drawing \(K_{2,3}\) this way and you'll find that it's not possible to arrange the vertices in a way that satisfies the condition of outerplanarity due to the crossing of edges.

Deductive reasoning about subgraphs of outerplanar graph \(G\)

Knowing that neither \(K_{4}\) nor \(K_{2,3}\) can be drawn as outerplanar, assume for contradiction that a graph \(G\) is outerplanar and contains a subgraph homeomorphic to \(K_{4}\) or \(K_{23}\). But this would mean that we could draw \(G\) such that all vertices lie on the exterior boundary, and at the same time, we would need to draw the subgraph \(K_{4}\) or \(K_{23}\), which was proven impossible in steps 1 and 2. So this assumption leads to contradiction, meaning no outerplanar graph \(G\) should contain a subgraph homeomorphic or contractible to \(K_{4}\) or \(K_{23}\).

Key concepts

Planar Graph

A planar graph is a type of graph that can be drawn on a flat surface, such as a piece of paper, without any of the edges crossing over each other. Every planar graph divides the plane into distinct regions called faces. One of these faces is the unbounded region outside the graph known as the infinite face or exterior.

In the given exercise, understanding whether a graph is planar or not helps in determining if it can be considered an outerplanar graph. It's crucial to recognize that outerplanar graphs are a subset of planar graphs where not only can the graph be drawn without edge crossings, but all vertices must also reside on the boundary of the exterior face.

Kuratowski's Theorem

Kuratowski's theorem is a significant result in graph theory that characterizes planar graphs using subgraph relationships. It states that a graph is non-planar if and only if it contains a subgraph that is homeomorphic to the complete graph on five nodes, denoted as \(K_5\), or the complete bipartite graph on six nodes, denoted as \(K_{3,3}\).

A graph is homeomorphic to another if it can be transformed into the latter by a series of edge subdivisions, where an edge is divided by adding a new vertex along it. Therefore, if a graph can be reduced to \(K_5\) or \(K_{3,3}\) through edge contractions, it cannot be planar. This concept helps explain why certain graphs, like \(K_{4}\) and \(K_{2,3}\) posed in the exercise, are inherently non-outerplanar.

Homeomorphic Subgraphs

Homeomorphic subgraphs are derived from a graph by changing its structure through a process known as edge subdivision or edge contraction without losing the inherent graph properties. For instance, an edge subdivision could involve replacing a straight edge with two edges connected by a new vertex, thereby making the graph more intricate. Conversely, edge contraction involves removing an edge while merging its bounding vertices into a single vertex.

In the context of the exercise, recognizing homeomorphic subgraphs is crucial when analyzing whether \(K_4\) or \(K_{2,3}\) can ever be turned into an outerplanar graph. Since any outerplanar graph cannot contain subgraphs homeomorphic to \(K_4\) or \(K_{2,3}\), these operations help us understand the limitations of outerplanarity in terms of graph structure.

Bipartite Graph

A bipartite graph is one where its set of vertices can be divided into two distinct and disjoint subsets where every edge connects a vertex from the first subset to a vertex in the second subset, and there are no edges between vertices within the same subset. This kind of graph is symbolized as \(K_{m,n}\), where \(m\) and \(n\) are the numbers of vertices in each subset.

An example of this is the \(K_{2,3}\) graph mentioned in the exercise. Despite being bipartite, \(K_{2,3}\) cannot be drawn in an outerplanar fashion due to the inevitable edge crossings. Outerplanar bipartite graphs are particularly interesting as their structure disallows the complexity that would result in a non-outerplanar configuration, hence offering intuitive insights into the relationship between bipartiteness and outerplanarity.