## DIMACS TR: 93-44

## Half-integral flows in a planar graph with four holes

### Author: Alexander V. Karzanov

**
ABSTRACT
**

This report contains an improved and shorter proof of the four-hole flow
theorem obtained in an earlier paper of the author. Suppose we are given
an undirected planar graph G and a collection U of pairs of its vertices
to be connected by flows of unit value. We assume that the graph G+U is
eulerian, and that there is a subset H of faces of G such that each pair
in U belongs to the boundary of some face in H.
It is known, due to Okamura and Seymour, Okamura, Karzanov, that if |H| is
1, 2 or 3 and the multicommodity flow problem for G and U has a solution then
it has an integral solution as well. Such a property does not remain true
for |H|=4. We prove that if |H|=4 and if the problem for G and U has a solution
then it has a half-integral solution.

*** This report not available on line ***

Paper only.

DIMACS Home Page