The Setting
Let be a relation on a finite set , and let and be two families of pairs in . A pair of and a pair of conflict when (1)✦ The aim is to delete pairs from both families until no conflict is left, and to delete few.
Conflicts and Prunings
A conflict between and has the two points and . The sets and of and are the set of the points and the set of the points of all conflicts between a pair of and a pair of . Families and of pairs are conflict-free when no pair of conflicts with a pair of .✦
A pair covers a pair from the left when ✦, and a pair covers from the right when ✦. For a family of pairs, the left image is the set of the pairs covered from the left by a pair of ✦, and the right image is the set of the pairs covered from the right by a pair of ✦. A pair is covered by families and when it lies in .✦ The uncovered part of for and is the set of the points of not covered by them, (2)✦
A pruning of and is a pair of conflict-free families and that keep every pair of and of that is in no conflict between the two families, and that satisfy (3)✦
Matchings and Vertex Covers
Let be a finite bipartite graph with left side and right side , an edge being a pair . A matching of is a set of edges of no two of which share an end.✦ The matching number is the largest number of edges in a matching of , and a maximum matching of is a matching with edges.✦ A vertex cover of is a pair of sets and such that every edge of has or ; its size is .✦
For and , write and . An edge of starts in and ends in . The block is the bipartite graph on and whose edges are the edges of that end in , and the block is the bipartite graph on and whose edges are the edges of that start in . For a matching of , is the set of its edges that end in and the set of its edges that start in .
The Augmented Graph
The augmented graph of and is the bipartite graph with left side and right side , each side with its own copy of , in which a left vertex and a right vertex are joined when (4)✦ and two points of are never joined.
The blocks of are the bipartite graph between and , in which a point and a pair are joined when covers from the left✦, and the bipartite graph between and , in which and a pair are joined when covers from the right✦. A matching of has two parts: , its edges from to , taken as edges of ✦, and , its edges from to , taken as edges of ✦.
The Claim
Theorem 1. Let be a relation on a finite set , and let and be families of pairs in .
If has a maximum matching with (5)✦ then and have a pruning.
has a matching whose parts and satisfy (6)✦
Let be a finite bipartite graph with left side and right side .
If is a maximum matching of , then has a vertex cover with (7)✦ in which every vertex of and of lies on an edge of .
If is a vertex cover of of least size, then has a matching with (8)✦
Let moreover and be such that every edge of that ends in starts in .
If a maximum matching of satisfies (9)✦ then is a maximum matching of .
has a matching with (10)✦
What Is Checked
The claims are stated over the matchings, maximum matchings and vertex covers of a finite bipartite graph and of its blocks, and over the augmented graph of and , defined by (4) from the conflicts and from covering from the left and from the right, with its blocks and , the parts and of its matchings, the sets and , the uncovered part (2) and the prunings (3).