How to quickly yet convincingly claim that edge contractions preserve outerplanarity

408 Views Asked by At

Let $G$ be a simple outerplanar graph with $n$ vertices. Let the vertex $v \in V(G)$ have degree 2 and be a member of a bounded face formed by a chordless cycle $C$ of more than 3 vertices.

enter image description here

Given the above conditions, I want to prove that another outerplanar graph $G'$ with $n-1$ vertices can always be found.

My current proof is as follows:

Because the degree of $v$ is 2, we know there are only two edges incident to $v$, namely $(v, v_0)$ and $(v, v_1)$. If we contract the edge $(v, v_0)$ by adding the edge $(v_0, v_1)$ and removing all edges incident to $v$, the resulting graph $G'$ will also be outerplanar since edge contractions preserve outerplanarity.

enter image description here

The part that I'm unsure about is this:

the resulting graph $G'$ will also be outerplanar since edge contractions preserve outerplanarity.

I know the type of edge contractions I'm doing here preserve outerplanarity, but that doesn't seem like an obvious enough claim to leave unsupported. Is there an accepted theorem I could cite to back this claim up? Should I include a proof related to that specific claim? Or does it seem ok to just leave that claim as it is? I'd rather not include a proof for this if there's an accepted theorem I could cite, since this is a one lemma in a fairly long proof that already has several.

1

There are 1 best solutions below

0
On BEST ANSWER

The easiest way to justify the claim is the fact that a graph is outerplanar if and only if it does not contain the graphs $K_4$ or $K_{2, 3}$ as a minor. A graph $H$ is a minor if a graph $G$ if $H$ can be obtained from $G$ by a sequence of edge contractions, edge deletions, and vertex deletions.

In case you're not allowed to cite the theorem, here's a more direct way to prove the claim. Let $G$ be an outerplanar graph. As $G$ is outerplanar every vertex is on the outer face, so the outer face must be a collection of cycles connected by paths. Without loss of generality, we assume $G$ is 2-connected, so the outer face of $G$ is a single cycle. When contracting an edge of $G$ there are two cases to consider: either the edge is on the outer face, or it is a chord. Contracting an edge on the outer face yields a new graph whose outer face is a cycle with $n - 1$ vertices, hence the resulting graph is outerplanar. Contracting a chord yields a graph whose outer face is two cycles that share one vertex in common. Hence, the resulting graph is outerplanar (although, it is no longer 2-connected).