If a graph has no K4 or K2,3 subdivision then it is outerplanar

Question

Is this a valid argument to prove the claim? I put in bold the part I am doubting the most:

If a graph has no $K_{4}$ or $K_{2,3}$ subdivision then it is outerplanar

Suppose G has no $K_{4}$ or $K_{2,3}$. Add a vertex $v$ to the exterior face of $G$ (outside of $G$) and connect it to every vertex in $G$. Call this graph $G^{\prime}$. Assume $G^{\prime}$ is not planar and by Kuratowski theorem contains a $K_{5}$ or $K_{3,3}$ subdivision. Therefore $G$ must contain a $K_{4}$ or $K_{2,3}$ subdivision, as every $K_{5}$ subdivision contains a $K_{4}$ and every $K_{3,3}$ contains a $K_{2,3}$ subdivision. However, by assumption $G$ does not have a $K_{4}$ or $K_{2,3}$ subdivision, hence we have a contradiction. Hence $G^{\prime}$ must be planar. As $G^{\prime}$ is planar and $v$ is exterior to all of $G$ and adjacent to all vertices in $G$, $G$ must be outerplanar.

Answer 1

First, you begin by adding vertex $v$ to the "exterior face of $G$", and later using the fact that $v$ is "exterior to all of $G$".

This is not okay, since at this point, we don't know that $G$ is planar, and don't have a fixed plane embedding of $G$. Even if you invoke Kuratowski's theorem to say that $G$ is planar and pick a plane embedding, it might be the wrong embedding for us to use later! We will prove that $G'$ has a plane embedding later on, but that plane embedding might not be compatible with the plane embedding we picked for $G$.

(Note also that even if $G$ is outerplanar, not all planar embeddings of it are outerplanar embeddings. Some embeddings might have all vertices along a face that is not the exterior face; others might have no such face at all.)

So in the first step, all we can do is say "contruct $G'$ by adding a new vertex $v$ adjacent to all vertices of $G$". This will be fine.

---

To justify the bolded step, consider a subdivision of, say, $K_5$ in $G'$.

• If it does not contain the new vertex $v$, we're fine; it's a subdivision of $K_5$ in $G$, and this contains a subdivision of $K_4$.
• If it contains $v$ along a subdivided edge, then forget about that entire subdivided edge. We get a subdivision of $K_5 - e$ in $G$, which still contains a subdivision of $K_4$.
• If it contains $v$ as one of the $K_5$ vertices, then forget about that vertex and all the subdivided edges out of it. We get a subdivision of $K_4$ in $G$.

The same argument works for $K_{3,3}$.

---

We have to be more careful with the last step: just because $G'$ is planar, can we conclude that $G$ is outerplanar?

Let's take a planar drawing of $G'$. Deleting $v$ and all its edges gives a planar drawing of $G$. Let $S$ be the subset of the plane where $v$ and all its edges were embedded. Then

1. $S$ is a connected subset of the plane which intersects no vertices or edges of $G$, so it's contained entirely in some face of $G$.
2. Since $S$ contains points arbitrarily close to where vertices of $G$ are embedded, that face of $G$ contains all the vertices.

So we have an embedding of $G$ where one of the faces contains all the vertices. If it is already exterior, fine. If not, we can invert the plane about a point contained in this face, and get a new embedding of $G$ where it is the exterior face.