Assignment 8 due by the end of class Wednesday March 21 2001.
  1. Determine the thickness of K_{10}. Hint: show an upper bound and an equal lower bound.
  2. Show that every tree is planar by describing a simple algorithm to draw a tree in the plane, and explaining why your algorithm does not create any crossings.
  3. Trace the planarity testing algorithm from class on the graph from class (also described below), assuming that the initial cycle selected is (10,1,7,8,4,3,6,10). Also, briefly describe how the trace changes if edge (3,4) is removed from the graph. 
    cycle (10,1,11,12,15,14,2,16,3,6,10)
paths  (1,7,8,0,5,2) (10,13,12) (8,4,3) (5,9,6)
edges  (11,13) (0,4) (0,9) (11,14) (15,16) (3,10)
  4. Prove that any biconnected graph with no separating cycle is planar. Hint: first describe all such graphs.
  5. Suppose that C is a separating cycle of a biconnected graph G such that the interlacement graph of the pieces with respect to C contains a triangle.
    1. Prove that C contains vertices a,b,c,d,e,f (in this cyclic order, but not necessarily consecutive) such that some piece P_a has a path with endpoints a,d, some piece P_b has a path with endpoints b,e, some piece P_c has a path with endpoints c,f.
    2. Prove that G contains a subgraph homeomorphic to K_{3,3}. Hint: use the previous subquestion.