Graphs with no K3,3 Minor Containing a Fixed Edge

Abstract EN

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 a K3,3 minor 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 the main result of this paper, it is shown that the Ford-Fulkerson algorithm naturally extends to this more general class of graphs.