Prove that a planar graph is connected if it has $p$ vertices and $3p-7$ edges Let $p$ be an integer so that $ p\ge3$ and let $G$ be a planar graph having $p$ vertices and $3p-7$ edges. Prove that $G$ is connected.
I'm a little unsure of where to begin with this problem. It was suggested that I try to use Euler's Formula which states:
Let $G$ be a connected graph with $p$ verticies and $q$ edges. If $G$ has a planar embedding with $f$ faces then $p-q+f=2$
I'm not sure how helpful this is since it doesn't prove connectedness, but is just a property of connected graphs with planar embeddings.
 A: This is too long for a comment, even though it’s a long hint, and not a solution.
First of all, the only way I see to solve this is to use (or effectively prove) the result I mentioned about the maximum number of edges in a planar graph.
Try proving this by contradiction. Suppose a graph $G$ has $p$ vertices, where $p>3$, and $3p-7$ edges, and also assume $G$ is not connected. If you show this is impossible (reach a contradiction), you’ve proved your theorem.
Two ideas will be useful. First of all, if a planar graph $G$ with at least 3 vertices is not connected, how many edges can you add to it and still have a planar graph? At least two. (Do you see how to do this, and can you explain it?). If you add as many edges as possible without destroying planarity, the resulting graph will be connected. (Why?) So if there exists a non-connected planar graph $G$ with $p\ge3$ vertices at with $3p-7$ edges, then there is a planar graph $G'$ with $p$ vertices and at least $3p-5$ edges. It turns out this is impossible. $3p-5$ is more edges than a connected planar graph with $p$ vertices can have, and the second idea will be useful to prove that.
The regions in a graph are polygons with at least 3 sides/edges each.  Suppose you know $q$ and $r$ for a particular planar connected graph. Can you determine the average number of edges per region of $G$? For example, if $q=11$ and $r=4$, the average number of edges per region is $\frac{11}{2}$. (Draw pictures to convince yourself and come up with a general formula for the average number of edges per region, given $q$ and $r$.) The hypotheses you have for $G'$, along with Euler’s formula, which holds for $G'$ because $G'$ is connected and planar, allow you to find $q$ in terms of $r$. This allows you to say something about the average number of edges around a region, and what it says turns out to be impossible.
A: There is a more generalized version of Euler's formula that holds for any graph. Suppose $G$ is a planar graph with $p$ vertices, $q$ edges, and $c$ components: $G_1, G_2, \dots, G_c$. Assume $G_i$ has $p_i$ vertices and $q_i$ edges. Since $G$ is planar, it has a plane embedding $\cal{E}$, and suppose $G$ has $f$ faces in $\cal{E}$. Consider the embedding $\cal{E_i}$ of $G_i$ obtained by restricting $\cal{E}$ to $G_i$, and assume $G_i$ has $f_i$ faces in this embedding. Then by Euler's formula:
$$\sum_{i=1}^c (p_i - q_i + f_i) = \sum_{i=1}^c 2 \\
p - q + \sum_{i=1}^c f_i = 2c$$
Now note that the outer face of $G$ in $\cal{E}$ is counted in each $f_i$, so we have:
$$p - q + (f + c-1) = 2c \\
p - q + f = c + 1$$
Now consider a planar graph $G$ with $p$ vertices, $q = 3p-7$ edges, and $c$ components. There is a plane embedding of $G$, and suppose $G$ has $f$ faces in that embedding. Since $G$ is simple, each face has at most 3 edges on its boundary, and $f \leq \frac{2}{3}q$. So you know:
$$\begin{align}c &= p - q + f - 1 \\
&\leq p - (3p-7) + \frac{2}{3}(3p-7) - 1 \\
&= \frac{4}{3}
\end{align}$$
Thus $c=1$, and $G$ is connected.
