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
4-vertex 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 2n-4 edges.
(Hint: use Euler's formula, and mimic the proof that a planar graph has at
most 3n-6 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.