Изменения

Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.  '''База :''' для <tex>n=1</tex> очевиднаочевидно. Докажем индукционный  '''Индукционный переход :''' Пусть верно для <tex>n-1 \rightarrow </tex>, докажем для <tex>n(n>1</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex> Тогда <tex>|U|=\alpha(H) \le m-1</tex>, следовательно <tex>v(H-U) \ge (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \le m-1</tex>.По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к ксторой которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex>{<tex>a</tex>} не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.