Show if $G$ is a planar graph, then $G\setminus e$ is also planar

249 Views Asked by At

Show if $G$ is a planar graph, then graph $G\setminus e$ is also planar.

The exercise is pretty obvious while reading it, but I had some struggles solving it. Using the notation $n=|V(G)|$, $m=|E(G)|$ and $f=|S(G)|$ (number of faces), I thought about proving the statement from Euler's formula, which states that if graph $G$ is planar, then the formula $$n-m+f=2$$ is true.

My proof: As I need to show the implication, we assume that $G$ is planar, thus $n-m+f=2$. Then we take out one of the edges $e$, so the number of vertices $n$ stays the same, but number of edges and faces is decreased by $1$, so the formula changes to $$n-(m-1)+(f-1)=n-m+1+f-1=n-m+f=2$$ which means that the $G\setminus e$ is also a planar graph, which ends the proof.

Question: Is my proof correct and sufficient? I also thought about Kuratowski's Theorem, but I do not know how should I solve it then, so any tips would be appreciated.

2

There are 2 best solutions below

4
On BEST ANSWER

I think you're overthinking it. When you take out one of the edges (which you do as part of your proof), what is left is a drawing of $G\setminus e$ in the plane, ergo it is planar. You don't need to check that Euler's formula still holds.

2
On

Euler's formula says that if the graph is planar, then $n-m-f=2$. It does not say that if $n-m-f=2$, then the graph is planar.