Экстремальная теория графов: различия между версиями

==Условия минимальной степени ==
 
Упомянутые теоремы дают условия для появления небольших объектов внутри (возможно) большого графа. В качестве противоположных экстремумов, можно искать условие, которое вынуждает существование структуры, которая покрывает все вершины. Но граф с
:<math> \binom{n-1}{2} </math>
рёбрами может иметь изолированные вершины, хотя почти все возможные рёбра присутствуют в графе, что означает, что даже очень плотные графы могут не иметь интересующую нас структуру, покрывающую все вершины. Простое условие, опирающиесяопирающееся на подсчёт рёбер, не даёт информации, как рёбра распределены в графе, так что часто такое условие даёт неинтересные результаты для очень больших структур. Вместо этого, мы вводим понятие минимальной степени. Минимальная степень графа ''G'' определяется как
:<math> \delta(G)=\min_{v\in G} d(v) . </math>
Задание большой минимальной степени удаляет возражение, что могут существовать «патологические» вершины. Если минимальная степень графа ''G'' равна 1, например, то не может быть изолированных вершин (даже если ''G'' содержит очень мало рёбер).