Докажите, что граф G регулярен тогда и только тогда, когда G содержит такую вершину v, что degGv = δ(G) и degGv = δ(G). (Здесь δ(H) — минимальная степ ...
Дан выпуклый многогранник, имеющий только треугольники в качестве граней. Все степени вершин многогранника не меньше пяти (в графовом смысле), и, кром ...
Задача следующая: доказать, что в графе на $%k$% вершинах, в котором максимальная степень вершины не превышает трёх и $%k$% четно, всегда можно выбрат ...
Существуют ли последовательности графов, у которых степени вершин подчиняются степенному закону, а вторые степени вершин (в каком-нибудь определении) ...
Дано дерево на семи вершинах. Известно, что в этом дереве по меньшей мере три вершины имеют степень 1, и как минимум две вершины имеют степень 3. Найд ...
Рассмотрим граф на n вершинах. Доказать, что в нем существует подмножество S вершин исходного графа, такое что мощность S не меньше $% \sum_{i=1}^n \f ...