Formule de Tutte-Berge

Intuitivement, pour tout sous-ensemble U des sommets, la seule façon de couvrir complètement une composante impaire de G − U par un couplage implique que l'une des arêtes figurant dans le couplage est incidente à U. Si en effet une composante impaire n'avait pas d'arête du couplage la reliant à U, alors la partie du couplage qui couvre la composante couvrirait ses sommets par paires, mais comme la composante a un nombre impair de sommets, il y aurait nécessairement au moins un sommet restant et non couplé. Par conséquent, si, pour un choix, l'ensemble U a peu de sommets mais que sa suppression crée un grand nombre de composantes impaires, alors il y aura de nombreux sommets non couplés, ce qui implique que le couplage lui-même est petit. Ce raisonnement peut être précisé en affirmant que la taille d'un couplage maximal est au plus égale à la valeur donnée par la formule de Tutte-Berge.

La caractérisation de Tutte et Berge prouve que c'est le seul obstacle à la création d'un grand couplage : la taille du couplage optimal est déterminée par le sous-ensemble U qui donne la plus grande différence entre le nombre de composantes impaires en dehors de U et le nombre de sommets de U. Autrement dit, il existe toujours un sous-ensemble U tel que la suppression de U crée le nombre correct de composantes impaires nécessaire pour que la formule soit vraie. Une façon de déterminer un tel ensemble U est de choisir n'importe quel couplage maximal M, et de définir un ensemble X comme l'ensemble des sommets qui sont non couplés dans M, ou qui peuvent être atteints à partir d'un sommet non couplé par un chemin alterné qui se termine par une arête couplée. Soit U l'ensemble des sommets qui sont couplés par M avec des sommets de X. Deux sommets de X ne peuvent pas être adjacents, car s'ils l'étaient, leurs chemins alternés pourraient être concaténés pour donner un chemin par lequel le couplage pourrait être augmenté, contredisant la maximalité de M. Chaque voisin d'un sommet x dans X doit appartenir à U, sinon on pourrait prolonger un chemin alterné vers x par une autre paire d'arêtes vers le voisin, faisant du voisin un élément de U. Par conséquent, dans G − U, chaque sommet de X forme une composante à un seul sommet, de taille impaire. Il ne peut y avoir d'autres composantes impaires, car tous les autres sommets restent couplés après la suppression de U. Donc, avec cette construction, la taille de U et le nombre de composantes impaires créées en supprimant U réalisent la formule.

Le théorème de Tutte caractérise les graphes avec des couplages parfaits comme étant ceux pour lesquels la suppression d'un sous-ensemble ${\displaystyle U}$ de sommets crée au plus ${\displaystyle |U|}$ composantes impaires. (Un sous-ensemble '${\displaystyle U}$ qui crée au moins ${\displaystyle |U|}$ composantes impaires peut toujours être réalisé avec l'ensemble vide . ) Dans ce cas, selon la formule de Tutte–Berge, la taille du couplage est ${\displaystyle |V|/2}$ ; autrement dit, le couplage maximal est un couplage parfait. Ainsi, le théorème de Tutte peut être dérivé de la formule de Tutte-Berge, et la formule peut être vue comme une généralisation du théorème de Tutte.

• Dureté d'un graphe ou la façon de créer de nombreuses composantes connexes en supprimant un petit ensemble de sommets sans tenir compte de la parité des composantes.
• Théorème du mariage de Hall
• Théorème de Tutte