Задача
COM-B2-M07-P013 Дерево с совершенным паросочетанием
#13
★★★★☆ Уровень 4 из 5
В дереве есть совершенное паросочетание. Докажите, что сосед каждого листа соединён в этом паросочетании именно с этим листом.
Лист имеет только одно ребро, которым его можно покрыть.
Пусть \(x\) — лист, а \(y\) — его единственный сосед. В совершенном паросочетании вершина \(x\) должна быть покрыта каким-то ребром. Единственное ребро, инцидентное \(x\), — это \(xy\). Следовательно, ребро \(xy\) обязательно входит в паросочетание.
Маленькая, но важная matching-лемма для деревьев.