Graphs with no K3,3 Minor Containing a Fixed Edge

It is well known that every cycle of a graph must intersect every cut in an even number of edges. For planar graphs, Ford and Fulkerson proved that, for any edge e , there exists a cycle containing e that intersects every minimal cut containing e in exactly two edges. The main result of this paper generalizes this result to any nonplanar graph G provided G does not have aK 3 , 3minor containing the given edge e . Ford and Fulkerson used their result to provide an efficient algorithm for solving the maximum-flow problem on planar graphs. As a corollary to themain result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs.