Верхняя оценка числа максимальных независимых множеств графа

Пусть $T(G)$ – число максимальных независимых множеств, $M(G)$ – число порожденных паросочетаний графа $G$. Доказывается, что $T(G)\le M(G)+1$. Как следствие выводится оценка $T(G)\le((m-m_1)/p+1)^p+m_1$ для графа, не содержащего порожденного подграфа $(p+1)K_2$, здесь $m$ – число ребер, а $m_1$ – число доминирующих ребер. Это неравенство отличается от предположения, высказанного Балашем и Ю только наличием последнего слагаемого.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 06-01-00553а.