В графе на 30 вершинах (необязательно двудольном) между любыми тремя вершинами есть хотябы два ребра. Докажите, что в графе есть совершенное паросочетание (из 15 рёбер).

Заметим, что из 4-х вершин всегда можно выбрать совершенное паросочетание на двух ребрах.
Рассмотрим вершины 1, 2, 3 и 4. Среди вершин 1, 2, 3 есть хотя бы 2 ребра. Пусть это будут ребра между вершинами 1, 2 и 2, 3. С другой стороны, среди вершин 1, 3, 4 есть хотя бы 2 ребра. Тогда не умаляя общности имеем 2 варианта. Если это ребра между вершинами 1, 4 и 4, 3, тогда возьмем паросочетание из вершин 1, 2 и 4, 3. Если это ребра между вершинами 1, 3 и 3, 4, тогда возьмем паросочетание из вершин 1, 2 и 3, 4. Если же ребер будет больше, то все равно можно будет выбрать паросочетание на двух ребрах. Тогда для начала возьмем из графа две вершины, соединенные ребром, и удалим их и ребра, исходящие из этих вершин. Затем из оставшихся 28 вершин можно выделить паросочетание на 14–и ребрах, выбирая какие-то 4 вершины, выделяя из них паросочетание на 2–х ребрах и удаляя эти 4 вершины. Добавим к этому паросочетанию исходную пару и получим паросочетание на 15 ребрах.