A min-max property of bipartite graphs is stated; it is a variation on the theorem of Kiinig 'maximum x%zhing= minimum covering'; one shows that a c&&i inequaliw holds for any graph and the equality for bipartite graphs is derived from a simple network flow model.
-.
Various extensions of the theorem of
Kiinig 'chromatic index ot L: bipartite graph =maximum degree' have been made; among them, some are concerned with equitab3e colourings [3]. In this note we present a variation on the theorem of Kijnig 'maximum matching = minimum covering' which has a flavour of equitable coloring. Let G = (X, Y, E) be a simple bipartite graph; given a subset F of edges of G, we denote by f(x) the number of edges in F which are adjacent to node x. Two disjoint subsets FI, F2 in E form an equitable pair 3 for each node z we have -1 sfi(z) -fi(z) s 1. We shall be interested in the value p(G) = max{l&l-IF21 1 F,, Fz equitable pair in G}; notice that p(G) is at least as large as the maximum cardinality v(G) of a matching in G. We may have a strict inequality as can be seen in the example of Fig. 1. An S-couer a of G' is a collection of nodes and edges defined as follows: it contains a subset S of nodes in G and all edges which have either both nodes or no node in S. We can now formulate the following variation oa the theorem of Kiinig [l, Ch. IO].