Such graph $G^*$ is planar, if and only if $G$ is outerplanar

751 Views Asked by At

Let $G$ be a graph and add a new vertex $v$ outside of $G$, then connect vertex $v$ with all the vertices in $G$, which denote by $G^*$, to prove graph $G^*$ is planar, if and only if $G$ is outerplanar.
I'm trying to start with the theorem, for a planar graph with $n \geq 3$ vertices, we have $m \leq 3n-6$, but it's don't work.
Any help is appreciated

1

There are 1 best solutions below

0
On

An outerplanar graph is defined as a graph where all vertices are in the outer face. This means the statement is clearly true in the if direction.

For the only if direction, suppose $G$ is not outerplanar. Then there exists a vertex $x$ that does not belong to the outer face, and therefore the edge $vx$ must cross another edge, meaning $G^*$ is not planar.