Math/CS L320
Fall, 2008
hw7

This homework is due Thursday, November 20.

  1. Euler's theorem for planar connected graphs says 
    	F - E + V = 1
    where F is the number of regions, E the number of edges and V the number of vertices.

    Discover and then prove a generalization for a planar graph with C connected components. Your formula should reduce to Euler's when C=1.

  2. On page 124 of Richeson's book Euler's Gem you can find the following proof that K5, the complete graph on five points, is not planar.

    Suppose K5 is a planar graph. Then we can draw K5 in the plane so that no edges cross. K5 has 5 vertices and 10 edges. Euler's formula for planar graphs states that V-E+F=2 [counting the outside of the graph as one of the faces], thus our planar drawing of K5 must have 7 faces including the unbounded face (because 2 = 5 - 10 + F).

    Each edge borders two faces, so 2E = pF, where p is the average number of sides on all faces. K5 is a complete graph, so it has no loops or parallel edges. Because there are no loops, there are no faces bounded by only one edge, and because there are no parallel edges there are no faces bounded by two edges. Thus the average number of edges per face is at least three. So, p >= 3 and 2E >= 3F. But F = 7 and E = 10 implies that 20 >= 21, which is a contradiction. It must be that K5 is non planar.

    In a similar way we can prove that the complete bipartite graph K3,3 is not planar (give it a try!). The key difference is that because K3,3 is bipartite, a path that begins and ends at the same vertex must have an even number of edges. So there can be no three-sided faces either.

    Your job: complete the proof suggested in the previous paragraph.

  3. Find the largest and smallest number of edges that a graph with N vertices can have if it is
    1. connected
    2. not connected
    3. complete
    4. bipartite
    5. vertex three colorable
    6. vertex k-colorable

    (Professor Zara will talk Thursday about coloring graphs.)

    You might want to draw pictures for, say, N=5, before you tackle the general case.