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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.