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

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.

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.