Prove that a connected graph with $n$ vertices and $n+2$ edges is planar. 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?
 A: 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.)
A: 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$
