Question: In class we saw that every planar graph has at most 6n edges. This bound is appallingly weak: in fact every planar graph with at least 3 nodes has at most 3n-6 edges. Prove this. (You can still assume that any planar graph can be drawn with straight lines.)
Answer: Draw a graph. Triangulate it so that all open spaces in the graph have only three edges surrounding it - including the outside of the graph. This only increases the number of edges, so an upper bound on the number of edges in this new graph is also an upper bound on the number of edges in the original graph.
Start with:
o---o---o
| / \ /
o-o o
| \ / \
o---o---o
End with:
_____
/ \
/---o---o---o
| /|\ / \ /|
| | o-o---o |
| \|/ \ / \|
| o---o---o
| \_____/ \
\____________/
This is still planar and can be drawn with straight lines. Assume we
have done this.
Let T be the number of triangles in the graph. The total angles inside the triangles is 180T. We can also count the angles outside the graph. Since the graph lies entirely within a triangle the sum of the angles outside the graph is 3*360-180=900. So the sum of angles is 180T+900. The total of the angles is also 360n. So we have 180T+900 = 360n. Hence T=2n-5.
Now consider the number of edges. Each triangle has three edges, so m <= 3T. But in fact this double-counts all but the three edges outermost edges, so 2(m-3) + 3 <= 3T. Hence we have m <= (3T+3)/2.
If we put these two facts together we have m <= (3(2n-5)+3)/2 = 3n-6, which is what we want.
Question: Where in the above did we assume that we have at least 3 nodes?