Perfect Triangle Families

THEOREM 1. IfGis a planar oriented graph, then the minimum cardinality of an edge set containing at least one edge of each cyclic triangle ofG is equal to the maximum number of mutually edge-disjoint cyclic triangles in G. This theorem will be a corollary of a stronger result. For an oriented graph G, let T(G) denote the set of its cyclic triangles. For aT c T(G), denote by v(T) the maximum number of pairwise edge-disjoint triangles in T, and by T(T) the minimum cardinality of an edge set sharing an edge with each TeT. THEOREM 2. IfG is planar, then T(T) = v(T) holds for every T <= T(G). The proof of Theorems 1 and 2 allows us to determine T(T) and v(T) by efficient algorithms for any given family T of cyclic triangles. THEOREM 3. IfG is planar andT c T(G), then a collection o/v(T) mutually edge- disjoint triangles ofT and a z(T)-element edge set containing at least one edge of each Te T can be found in polynomial time. There are several related problems which remain open; they are discussed in the concluding section. 2. The Proof