Теорема.

Пусть G обыкновенный (n,m,k)-граф. Тогда выполн-ся: n-k≤m≤(n-k)(n-k+1)/2.

Док-во: Iчасть: Проверим верхнюю оценку. Пусть G*-обыкнов. Граф, имеющий n-вершин, k-компонет связ-ти и наиб. возможное число ребер-m*. Покажем, что m*=(n-k)(n-k+1)/2 .Каждая компонента связ-ти гр-а G* явл. полным графом,поэтому ,можно считать n1≥n2≥…≥nk. Убедимся,что n2=1. Предположим n2>1,пусть U-некоторая вершина гр-а Kn2,удалим n2-1 ребер инцидентных вершине U. Добавим затем n1 ребер,соединяющих U с кажд. вершиной Kn1,т.е. перенесем верш-у U из 2-ой компаненты связ-ти в 1-ую. Т.к. n1>(n2-1) мы получим граф,имеющий n вершин, k-компанент связ-ей и больше,чем m* ребер,а это противоречит выбору гр-а G*=>n2=1и тогда n3=…=nk=1. Т.о. все ребра гр-а G* содержатся в полном графе Kn1и n1=n-(k-1),поэтому по лемме о рукопожатиях m*=(n1-1)n1/2,если подставим n1=n-(k-1),то получим m*.

II Нижняя оценка. Проверим ниж. оценку. Применим индукцию к числу ребер,если m=0, то n=k. Пусть m>0 предположим,что для всех графов с числом ребер меньшим чем m, оценка имеет место.

Рассм. граф (n,m,k)-граф.Пусть G1=G-e,где е-некоторое ребро графа G,тогда G1будет (n,m-1,k1)-графом,где K1≤K+1 в силу леммы2.И тогда мы получим m-1≥n-k-1,т.е. m≥n-k ч.т.д.

Следствие1.

Пусть G-обыкнов.(n,m) граф,если m>(n-2)(n-1)/2,то граф G связен.

Док-во: Пусть K-число компанент связ-ти G,если K≥2,то m≤(n-2)(n-1)/2,что невозможно =>K=1,т.е. граф G связен.

Следствие2.

Если G-произв.(n,m,k)-граф,то m≥n-k.