Tutte–Berge formula
In the mathematical discipline of graph theory the Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. It is a generalization of Tutte theorem on perfect matchings, and is named after W. T. Tutte (who proved Tutte's theorem) and Claude Berge (who proved its generalization). Statement. The theorem states that the size of a maximum matching of a graph formula_1 equals formula_2 where formula_3 counts how many of the connected components of the graph formula_4 have an odd number of vertices. Equivalently, the number of "unmatched" vertices in a  maximum matching equalsformula_5. Explanation. Intuitively, for any subset formula_6 of the vertices, the only way to completely cover an odd component of formula_7 by a matching is for one of the matched edges covering the component to be incident to formula_6. If, instead, some odd component had no matched edge connecting it to formula_6, then the part of the matching that covered the component would cover its vertices in pairs, but since the component has an odd number of vertices it would necessarily include at least one leftover and unmatched vertex. Therefore, if some choice of formula_6 has few vertices  but its removal creates a large number of odd components, then there will be many unmatched vertices, implying that the matching itself will be small. This reasoning can be made precise by stating that the size of a maximum matching is at most equal to the value given by the Tutte–Berge formula. The characterization of Tutte and Berge proves that this is the only obstacle to creating a large matching: the size of the optimal matching will be determined by the subset formula_6 with the biggest difference between its numbers of odd components outside formula_6 and vertices inside formula_6 . That is, there always exists a subset formula_6 such that deleting formula_6 creates the correct number of odd components needed to make the formula true. One way to find such a set formula_6 is to choose any maximum matching formula_17, and to let formula_18 be the set of vertices that are either unmatched in formula_17, or that can be reached from an unmatched vertex by an alternating path that ends with a matched edge. Then, let formula_6 be the set of vertices that are matched by formula_17 to vertices in formula_18. No two vertices in formula_18 can be adjacent, for  if they were then their alternating paths could be concatenated to give a path by which the matching could be increased, contradicting the maximality of formula_17. Every neighbor of a vertex formula_25 in formula_18 must belong to formula_6, for otherwise we could extend an alternating path to formula_25 by one more pair of edges, through the neighbor, causing the neighbor to become part of formula_6. Therefore, in formula_7, every vertex of formula_18 forms a single-vertex component, which is odd. There can be no other odd components, because all other vertices remain matched after deleting formula_6. So with this construction  the size of formula_6 and the number of odd components created by deleting formula_6 are what they need to be to make the formula be true. Relation to Tutte's theorem. Tutte's theorem characterizes the graphs with perfect matchings as being the ones for which deleting any subset formula_6 of vertices creates at most formula_36 odd components. (A subset formula_6 that creates at least formula_36 odd components can always be found in the empty set.) In this case, by the Tutte–Berge formula, the size of the matching is formula_39; that is, the maximum matching is a perfect matching . Thus, Tutte's theorem can be derived as a corollary of the Tutte–Berge formula, and the formula can be seen as a generalization of Tutte's theorem.