Proof that a graph with at most $n+2$ edges is planar

Question

Show that a connected, undirected graph $G=(V,E)$ with $n$ vertices and at most $n+2$ edges is planar. The only theorem I'm aware of to show that a graph is planar or not planar is kuratowskis theorem. So I have to show that a given graph with at most $n+2$ edges can't contain a subdivision that is $K_5$ or $K_{3,3}$.

My observations:

• a connected graph must contain at least $n-1$ edges. Otherwise the graph is not completely connected.
• $K_{3,3}$ has 6 vertices and each vertex has degree of 3.
• Similarly $K_5$ has 5 vertices and each vertex has degree of 5.

My idea: Show that a graph with at most $n+2$ edges does not contain 5 vertices with degree of 5 AND not 6 vertices with a degree of 3. Then it is not possible for the graph to contain either $K_{3,3}$ or $K_5$ as subdivision.

And from here I'm not sure on how to combine my observations into a proof. Do you have a hint for me here?

Answer 1

I propose this solution without Kuratowski's theorem.

1. If a graph $G'$ is obtained from a graph $G$ by removing a vertex of degree $1$ or by smoothing a vertex of degree $2$, then $G$ is planar if and only if $G'$ is planar and $|E(G')|-|V(G')|=|E(G)|-|V(G)|$.

2. It follows from 1 that we can assume that the degree of each vertex of graph $G$ is at least $3$.

3. By the handshaking lemma we obtain $$ 2(n+2)=\sum_{v\in G} \deg(v)\geq 3n\Rightarrow n\leq 4. $$ Since any graph on four vertices is planar, it follows that graph $G$ is planar.

Note. Not everything is as beautiful as we would like it to be.
If at any step as a result of smoothing a vertex of degree $2$ we get a graph with multiple edges, then we can replace all edges connecting these two vertices with a single edge. For the new graph $G'$ we get $|E(G')|-|V(G')|<2$ and still planarity $G$ is equivalent to planarity $G'$.
By the way, in this case it may happen that after multiple removal of all vertices of degree 1 and smoothing of vertices of degree 2 followed by replacement of parallel edges by a single edge we get $|V(G)|=1$ and then of course the 3th step is not needed.

Note 2. It is possible that someone does not like the process of smoothing the vertices of degree 2. Or the author of the question insists on going that way - this seems to me the right way, although here you have to use Kuratowski's theorem. In this case you can also reason this way.

Consistently removing vertices of degree $1$ (if necessary) we can assume that degrees of all vertices of graph $G$ are at least $2$.

If there are $k_d$ vertices of degree $d=2,3,4\ldots$, then $k_2+k_3+k_4+\ldots=n$ and by the handshaking lemma $$ 2(n+2)=\sum_{v\in G}\deg(v)=\sum_{d\geq2} k_d\cdot d=2n+\sum_{d\geq3} k_d(d-2) $$ Since $k_3+2k_4+3k_5+4k_6=4$, there are no vertices of degree greater than 6 and one of the following cases takes place:

-	$k_3$	$k_4$	$k_5$	$k_6$
1.	$0$	$0$	$0$	$1$
2.	$1$	$0$	$1$	$0$
3.	$0$	$2$	$0$	$0$
4.	$2$	$1$	$0$	$0$
5.	$4$	$0$	$0$	$0$

The following is clear.