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.

  • $\begingroup$ There is a well-known theorem that a connected planar graph with $q$ vertices can have no more than $3p-6$ edges. Can you use that theorem? (If so, suppose $G$ is not connected, and consider whether you can add some edges to $G$ without destroying planarity.) $\endgroup$ – Steve Kass Mar 21 '14 at 2:22
  • $\begingroup$ I've never heard of that theorem so I don't think I can just use that theorem to prove this. I'm not sure how to tell whether or not adding more edges would destroy the planarity $\endgroup$ – guest Mar 21 '14 at 2:31
  • $\begingroup$ You can use euler's formula to prove that theorem. $\endgroup$ – hbm Mar 21 '14 at 3:18
  • $\begingroup$ How can I do that? Doesn't Euler's Formula just tell me that if it were a connected graph then it would have that property? (Not that if it has that property then it is connected) How can it prove connectedness? $\endgroup$ – guest Mar 21 '14 at 3:32

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.

  • $\begingroup$ If you have a graph with 3 vertices, how can you add 2 edges to it without connecting all 3 together and creating a connected graph? $\endgroup$ – guest Mar 21 '14 at 4:31
  • $\begingroup$ I didn’t say the graph had to stay non-connected when you add the two more edges. It just has to remain planar. (Your question is insightful, because the new edges can go between separate components of the graph without destroying planarity.) $\endgroup$ – Steve Kass Mar 21 '14 at 4:32
  • $\begingroup$ What do you mean by adding at least 2 edges? I you can add 2 edges to the graph while maintaining the planarity, why can't you only add one? $\endgroup$ – guest Mar 21 '14 at 4:34
  • $\begingroup$ The proof I have in mind requires the assumption of a connected planar graph with at least $3p-5$ edges, which turns out to be impossible to have. For what it’s worth, and not important for the proof I’m thinking of, the number of edges you need to add to a non-connected graph to make it connected is (number of connected components of the non-connected graph) - 1. If the non-connected graph has only two connected pieces, you can connect it up with one edge. If it has 7 connected pieces, you can connect it up with 6 edges. But this isn’t important for the problem you have to solve. $\endgroup$ – Steve Kass Mar 21 '14 at 4:38
  • 1
    $\begingroup$ And I understand the whole first part as well. I found the theorem that a planar graph must have less than or equal to 3p-6 edges in my book. So I think I can use that as part of this proof without having to explicitly prove it $\endgroup$ – guest Mar 21 '14 at 4:44

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.