Теорема о максимальном числе ребер в графе

Пусть простой граф (нет петель и кратных ребер), пусть число вершин, число связных компонент, тогда максимальное число ребер в графе будет

.

Замечание. Для связного графа и , а это число ребер в полном графе.

Доказательство. Пусть -тая связная компонента, , тогда . Так как мы хотим получить максимальное число ребер, пусть все связные компоненты – полные графы, число ребер в ровно , а общая сумма ребер будет .

Наша цель: не меняя общего числа вершин и числа связных компонент, перестроить граф так, чтобы получить максимальное число ребер.

Рассмотрим две связные компоненты и , и пусть . Построим вместо них полные графы и с числом вершин и . Общее число вершин не изменилось, посмотрим, как изменилось число ребер:

Число ребер увеличилось, как минимум на 1.

Проделаем следующую процедуру:

выберем связную компоненту с наибольшим числом вершин и будем увеличивать число вершин в этой связный компоненте, за счет уменьшения числа вершин в других связных компонентах, при этом общее число ребер будет все время увеличиваться. Очевидно, оно достигает максимума, когда одна компонента будет полным графом с вершинами, а остальные компоненты будут изолированными вершинами и число ребер будет

.

Следствие. Если то и это максимальное число ребер при двух связных компонентах. Поэтому, если , то граф связный.