Assignment 7
due by the end of class Wednesday March 14 2001.

 Prove that if a graph has a cycle, then
it has an induced cycle with at least three vertices.
 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.

 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.)
 Prove that the maximum number of induced
4vertex paths in a graph is in O(n^4).
 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.)

Prove that a planar graph with no triangle has at most 2n4 edges.
(Hint: use Euler's formula, and mimic the proof that a planar graph has at
most 3n6 edges.)
 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.
 Bonus question: show that the number of paths in 2.2 is in Theta(n^4).
 Bonus question: give a O(n^5) time algorithm for problem 2.3.
 Research question: give an O(n^4) time algorithm for problem 2.3.