Independent paths and -subdivisions

A well-known theorem of Kuratowski states that a graph is planar iff it contains no subdivision of K 5 or K 3 , 3 . Seymour conjectured in 1977 that every 5-connected nonplanar graph contains a subdivision of K 5 . In this paper, we prove several results about independent paths (no vertex of a path is internal to another), which are then used to prove Seymourʹs conjecture for two classes of graphs. These results will be used in a subsequent paper to prove Seymourʹs conjecture for graphs containing K 4 − , which is a step in a program to approach Seymourʹs conjecture.