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.
Best Answer
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.