Prove that a connected graph with $n$ vertices and $n+2$ edges is planar.

Question

What I have tried is that a tree has $n-1$ number of edges. So if there are $n$ edges there would be a cycle. This cycle would contribute to one face of the graph. Similarly for the other 3 edges. I think this would add one face each to the graph. Is this reasoning correct?

Answer 1

Let $G$ be a connected graph on $n$ vertices with $n+2$ edges. Perform the following reductions on $G$.

If a vertex $v$ of $G$ has degree $1$, then $G$ is planar iff $G-v$ is plannar. Thus, we may remove all vertices of degree $1$ from $G$ successively, so that at the end, $G$ has no vertex of degree $1$.

If $v$ is a vertex of degree $2$ of $G$, then let $u$ and $w$ be neighbors of $G$. We remove $v$ from $G$ and add an edge $\{u,w\}$ to $G$. Note that $u$ and $w$ may already be adjacent, so this procedure can result in a multigraph, but that is not a problem. Indeed, if $u=w$ (i.e., $v$ is joined to $u$ by two edges), then this procedure removes $v$ and creates a loop at $u=w$. This procedure does not change planarity of the graph $G$.

The reduction steps can be performed only fintely many times. At the end, you will get a connected, possibly non-simple, graph $H$ each of whose vertices is of degree at least $3$. If $m$ is the number of vertices of the graph $H$, then it is still the case that $H$ has $m+2$ edges. However, by the Handshake Lemma, $$2(m+2)\geq 3m\,,$$ and we conclude that $m\leq 4$. It is easy to list all possible (not necessarily simple) connected graphs on $m$ vertices with $m\leq 4$ with $m+2$ edges, where the minimum degree is at least $3$, and check planarity for each of them.

The case $m=1$ has only $1$ nonisomorphic example. The case $m=2$ has $4$ nonisomorphic examples. The case $m=3$ has $5$ nonisomorphic examples. The case $m=4$ has only $1$ nonisomorphic example. (I hope I did not miscount.)

Answer 2

If $G=(V,E)$ is a simple graph, define $\epsilon(G)=|E|-|V|$. Some trivial observations:

• $\epsilon(G)$ is the sum of all $\epsilon(H)$ where $H$ runs over the connected components of $G$
• If $G$ is connected, then $\epsilon(G)\ge -1$
• If $G$ is connected and $\epsilon(G)=-1$, then $G$ is a tree
• If $G$ is connected and $\epsilon(G)=0$, then $G$ is a circle with trees sprouting from (some of) its vertices.

Claim. If $G$ is a simple connected graph with $\epsilon(G)\le 2$, then $G$ is planar.

Proof (by induction on $|V|$). If $n_d$ is the number of vertices of degree $d$, we have $$|V|=n_0+n_1+n_2+n_3+n_4+\ldots,\qquad 2|E|=n_1+2n_2+3n_3+4n_4+\ldots,$$ hence $$\tag14\ge 2\epsilon(G)=-2n_0-n_1+n_3+2n_4+3n_5+\ldots $$

Let $v$ be a vertex of minimal degree.

$\rho(v)=0$ can occur only for the one-point graph, which is clearly planar.

If $\rho(v)=1$, then removing $v$ and its edge produces a smaller connected graph $G'$ with $\epsilon(G')=\epsilon(G)$. By induction hypothesis $G'$ is planar, and it is a trivial task to add $v$ and its edge to a planar embedding of $G'$.

If $\rho(v)=2$ and $u,w$ (with $u\ne w$) are its neighbours, we remove $v$ and its edges and add an edge $uw$ (if it is not already there). The resulting $G'$ has $\epsilon(G')\le \epsilon(G)$, hence is planar by induction hypothesis. By inserting $v$ into one of the faces touching $uv$ in a planaer embedding of $G'$, joining $v$ to $u$ and $w$ within this face, and removing $uw$ (if it does not belong to $G$), we obtain a planar embedding of $G$.

Hence we may assume that $n_0=n_1=n_2=0$. Then $(1)$ gives us $$ |V|=n_3+n_4+\ldots\le n_3+2n_4+\ldots\le 4$$ and hence we obtain a planar embedding of $G$ from a planar embedding of $K_4$. $\square$