CSDS 455: Applied Graph Theory
Homework rules: You are welcome to work with others to solve these problems. If you do get help from
someone else (or from some other resource), please indicate that on your homework.
Problem 1: Prove that if we can solve the r-Vertex Disjoint Paths problem in polynomial time then we
can determine if G contains another graph H as a minor in polynomial time.