В математической дисциплине теории графов формула Тутта –Бержа является характеристикой размера максимального паросочетания в графе . Она является обобщением теоремы Тутта о совершенных паросочетаниях и названа в честь В. Т. Тутта (доказавшего теорему Тутта) и Клода Бержа (доказавшего ее обобщение).
Теорема утверждает, что размер максимального паросочетания графа равен , где — количество связных компонентов графа, имеющих нечетное число вершин.
Эквивалентно, количество непарных вершин в максимальном паросочетании равно
.
Интуитивно понятно, что для любого подмножества вершин единственный способ полностью покрыть нечетный компонент сопоставлением — это чтобы одно из сопоставленных ребер, покрывающих компонент, было инцидентно . Если бы вместо этого некоторый нечетный компонент не имел сопоставленного ребра, соединяющего его с , то часть сопоставления, покрывающая компонент, покрывала бы его вершины парами, но поскольку компонент имеет нечетное число вершин, он обязательно включал бы по крайней мере одну оставшуюся и несопоставленную вершину. Следовательно, если некоторый выбор имеет мало вершин, но его удаление создает большое число нечетных компонентов, то будет много несопоставленных вершин, что подразумевает, что само сопоставление будет небольшим. Это рассуждение можно уточнить, заявив, что размер максимального сопоставления не превышает значения, заданного формулой Тутте–Берже.
Характеристика Тутта и Бержа доказывает, что это единственное препятствие для создания большого паросочетания: размер оптимального паросочетания будет определяться подмножеством с наибольшей разницей между его количеством нечетных компонентов снаружи и вершинами внутри . То есть, всегда существует подмножество , такое, что удаление создает правильное количество нечетных компонентов, необходимое для того, чтобы формула была верной. Один из способов найти такое множество — выбрать любое максимальное паросочетание , и пусть будет множеством вершин, которые либо не сопоставлены в , либо до которых можно добраться из не сопоставленной вершины по чередующемуся пути , который заканчивается сопоставленным ребром. Затем пусть будет множеством вершин, которые сопоставлены с вершинами в . Никакие две вершины в не могут быть смежными, поскольку если бы они были, то их чередующиеся пути можно было бы объединить, чтобы получить путь, по которому сопоставление могло бы быть увеличено, что противоречит максимальности . Каждый сосед вершины в должен принадлежать , иначе мы могли бы расширить чередующийся путь до еще одной парой ребер через соседа, в результате чего сосед стал бы частью . Следовательно, в каждая вершина из образует компонент с одной вершиной, который является нечетным. Других нечетных компонентов быть не может, поскольку все остальные вершины остаются сопоставленными после удаления . Таким образом, при этой конструкции размер и количество нечетных компонентов, созданных удалением, являются тем, что им нужно, чтобы формула была верной.
Теорема Тутта характеризует графы с совершенными паросочетаниями как те, для которых удаление любого подмножества вершин создает не более нечетных компонентов. (Подмножество , которое создает не менее нечетных компонентов, всегда можно найти в пустом множестве .) В этом случае по формуле Тутта–Бержа размер паросочетания равен ; то есть максимальное паросочетание является совершенным паросочетанием. Таким образом, теорему Тутта можно вывести как следствие формулы Тутта–Бержа, а формулу можно рассматривать как обобщение теоремы Тутта.
