Variation on a theorem of König (Q797595): Difference between revisions

Let G be a bipartite graph. Two disjoint subsets \(F_ 1\), \(F_ 2\) of the edge set of G are said to form an equitable pair if, for each node x of G, the numbers of edges in \(F_ 1\), resp. \(F_ 2\) incident with x differ by at most one. An S-cover s of G is a subset S of nodes in G together with all edges having either both nodes or no node in S. Using network flow technique it is proved that, for G bipartite, \(\max \{| F_ 1| -| F_ 2|; F_ 1,F_ 2\) equitable pair in \(G\}= \min\{| s|;\) s an S-cover in G\}.