Lesson 3

At the lecture, the following theorem was stated. Theorem (Kuratowski). A graph is planar if and only if it contains no subgraph that is a subdivision of \(K_{3,3}\) or \(K_{5}\) (in other words, it is impossible to delete some vertices and edges so that what remains is a subdivision of  \(K_{3,3}\) or \(K_{5}\)).

In this step, several problems are presented that will guide you toward proving Kuratowski's theorem independently. If you are unable to prove a particular statement, you may omit its proof and proceed further (you may use the statement as though it has already been proved).

First, let's recall what a subdivision is. A graph \(H'\) is called a subdivision of a graph \(H\) if \(H'\) can be obtained from \(H\) by replacing some edges with simple paths (that is, each replaced edge \(xy\) is replaced by a simple \(xy\)-path). Moreover, all newly added vertices are distinct and have degree \(2\). The notation \(G \supset H\) means that \(G\) contains a subgraph that is a subdivision of the graph \(H\).

Prove the following lemma. Lemma. (Number 1, 5 points) A subdivision of a graph \(H\) is planar if and only if \(H\) is planar. We already know that both \(K_{5}\) and \(K_{3,3}\) are nonplanar. Therefore, if \(G \supset K_{5}\) or \(G \supset K_{3,3}\), then \(G\) is nonplanar. In the remainder of this section, we will try to prove the converse implication.

Lemma. (Number 2, 20 points) Let \(x,y \in V(G)\) and let \(xy \in E(G)\). Then the following statements hold.

• If \(G \cdot xy \supset K_{3,3}\), then \(G \supset K_{3,3}\).


• If \(G \cdot xy \supset K_{5}\), then \(G \supset K_{5}\) or \(G \supset K_{3,3}\).

Now, we proceed to the proof of Kuratowski's theorem. Theorem (Kuratowski). A graph is planar if and only if it contains no subgraph that is a subdivision of \(K_{3,3}\) or \(K_{5}\) (in other words, it is impossible to delete some vertices and edges so that what remains is a subdivision of  \(K_{3,3}\) or \(K_{5}\)).

Proof. As we already know, if a graph contains a subdivision of \(K_{3,3}\) or \(K_{5}\), then it is nonplanar.

For the converse implication, assume the contrary and consider a minimal counterexample \(G\), that is, a nonplanar graph containing no subdivisions of \(K_{5}\) or \(K_{3,3}\). Every graph with fewer vertices than \(G\), or with the same number of vertices but fewer edges, and containing no subdivisions of \(K_{5}\) or \(K_{3,3}\), is necessarily planar.

Lemma. (Number 3, 5 points) The graph \(G\) has no loops and no multiple edges. Moreover \(G\) is connected.

Lemma. (Number 4, 10 points) The graph \(G\) is \(2\)-connected.

Lemma. (Number 5, 15 points) The graph \(G\) is \(3\)-connected.

Lemma. Let \(G\) be a \(3\)-connected graph distinct from \(K_{4}\). Then there exists an edge \(e \in E(G)\) such that the graph \(G \cdot e\) is \(3\)-connected. Proof. Assume for contradiction that \(G \cdot e\) is not \(3\)-connected for every \(e \in E(G)\). For an edge \(xy\), let \(v_{xy}\) be the vertex obtained by contracting \(xy\) in \(G \cdot xy\).

Lemma. (Number 6, 5 points) For every edge \(xy\) there exists a vertex \(z \notin \{x,y\}\) such that \(G - \{x,y,z\}\) is disconnected.

Call any set \(S\) of three vertices with \(G-S\) disconnected a separation triple, and call the components of \(G-S\) the split components of \(S\).

Lemma. (Number 7, 5 points) If \(S=\{p,q,r\}\) is a separation triple and \(D\) is any split component of \(G-S\), then each vertex of \(S\) has a neighbor in \(D\).

So, there exists at least one separation triple arising from some edge. Among all choices of an edge \(xy\), a vertex \(z\), and a split component \(D\) of \(G-\{x,y,z\}\), choose \((x,y,z,D)\) so that \(|V(D)|\) is minimal. Then, \(z\) has a neighbor \(a \in V(D)\). Note that \(a\) has no neighbors outside \(D \cup \{x,y,z\}\), since otherwise \(a\) would connect \(D\) to another split component of \(G-\{x,y,z\}\).

(Number 8, 15 points) Finish the proof. ◼

Now, clearly, \(G \ne K_{4}\), then there exists an edge \(xy \in E(G)\) such that the graph \(G \cdot xy\) is \(3\)-connected; denote \(w = x \cdot y\). Hence, we have \(G \cdot xy \not\supset K_{5}\) and \(G \cdot xy \not\supset K_{3,3}\); hence the graph \(G \cdot xy\) is planar.

Let \(G' = G \cdot xy - w\), which is clearly isomorphic to \(G - x - y\). Consider a plane embedding of \(G'\) obtained from an embedding of \(G \cdot xy\) by deleting the vertex \(w\). Let \(q\) be the face of \(G'\) on which the vertex \(w\) was located.

(Number 9, 25 points) Finish the proof.

◼