Изменения

# Пусть $G$ - регулярный граф степени $k$, $U \subset V$, $U$ содержит нечетное число вершин и $m$ - число ребер, которые соединяют вершины $U$ с вершинами $V \setminus U$. Тогда $m$ четно тогда и только тогда, когда $k$ четно.

# Докажите, что в двусвязном кубическом графе есть полное паросочетание.

# Приведите пример кубического графа, в котором нет полного паросочетания.

# Пусть $G$ - регулярный граф степени $k$ с четным числом вершин, причем $\lambda(G) \ge k-1$. Докажите, что если удалить из $G$ не более $k - 1$ ребра, получившийся граф будет иметь полное паросочетание.

# Докажите, что если в графе $G$ есть соцветие $C$ и черенок достижим из вершины $u$, то в $G$ есть дополняющая цепь из вершины $u$ тогда и только тогда, когда она есть в графе $G/C$ (обратите внимание, она не обязана проходить через черенок, в отличие от леммы, рассказанной на лекции).

</wikitex>