Assignment 7 due by the end of class Wednesday March 14 2001.
    1. Prove that if a graph has a cycle, then it has an induced cycle with at least three vertices.
    2. Describe briefly but carefully how depth first search could be modified to return the vertices of an induced cycle with at least three vertices, whenever an input graph has a cycle.
    1. Describe an O(n^2) time algorithm which determines whether a given induced path (v1,v2,v3,v4) extends into an induced cycle with at least five vertices. (Hint: use an adjacency matrix, remove from the graph all vertices which cannot be part of such cycle, and then try to find a path which extends the given path into an induced cycle.)
    2. Prove that the maximum number of induced 4-vertex paths in a graph is in O(n^4).
    3. Briefly describe an O(n^6) time algorithm which determines whether a given graph contains an induced cycle with at least five vertices. (Hint: use the previous two questions.)
  1. Prove that a planar graph with no triangle has at most 2n-4 edges. (Hint: use Euler's formula, and mimic the proof that a planar graph has at most 3n-6 edges.)
  2. Prove that the crossing number of K3,3 is exactly 1. Hint: there are two parts to this question; you need to show that it is at most 1 and that it is at least 1. The first part is easy: give a drawing. The second part can be shown in many ways; the easiest uses the previous question.

The following questions are optional.

  1. Bonus question: show that the number of paths in 2.2 is in Theta(n^4).
  2. Bonus question: give a O(n^5) time algorithm for problem 2.3.
  3. Research question: give an O(n^4) time algorithm for problem 2.3.