HALF-INTEGRAL FLOWS IN A PLANAR GRAPH WITH 4 HOLES

Suppose that G = (VG, EG) is a planar graph embedded in the euclidean plane, that I, J, K, O are four of its faces (called holes in G), that s(1),...,s(r), t(1),...,t(r), are vertices of G such that each pair { s(i),t(i)} belongs to the boundary of some of I,J,K,O, and that the gr aph (VG, EG boolean OR {{s(1),t(1)},...,{s(r),t(r)}}) is eulerian. We prove that if the multi(commodity)flow problem in G with unit demands on the values of flows from s(i) to t(i) (i = 1,..., r) has a solution then it has a half-integral solution as well. In other words, there e xist, path P-1(1), P-1(2), P-2(1), P-2(2),...,P-r(1), P-r(2) in G such that each P-i(j) connects s(i) and t(i), and each edge of G is covere d at most twice by these paths. (It is known that in case of at most t hree holes there exists edge-disjoint paths connecting s(i) and t(i), i = 1,...,r, provided that the corresponding multiflow problem has a s olution, but this is, in general, false in case of four holes.)