Some Min-Max Formulations for Partitioning Problems in Graphs and Hypergraphs

We shall consider here the theorems of König for bipartite graphs and present some simple variations and extensions. For all graph-theoretical terms the reader is referred to C. Berge /1/. Following L.E. Trotter /2/, we may formulate the theorems of König in the following way: THEOREM OF KÖNIG I: In a bipartite graph G, the maximum size of a set of mutually non adjacent edges is equal to the minimum number of sets of mutually adjacent edges covering all edges.THEOREM OF KÖNIG II: In a bipartite graph G, the maximum size of a set of mutually adjacent edges is equal to the minimum number of sets of mutually non adjacent edges covering all edges.