Какие методы существуют для определения минимальной степени вершин в графе?

Возможно, имелись в виду некоторые из следующих методов определения минимальной степени вершин в графе:

• Использование теоремы Эйлера. 15 Она гласит, что сумма степеней вершин графа равна удвоенному числу его рёбер. 15 Это утверждение следует из того, что каждое ребро инцидентно двум вершинам, и в сумму степеней вершин графа ребро вносит двойку. 15
• Удаление вершин. 4 Можно удалять из графа одну за другой вершины с определённой степенью и получать подграфы. 4 В итоге на определённом шаге получится граф, в котором минимальная степень вершин будет не менее заданного значения. 4
• Использование неравенств. 3 Например, для любого графа G верны неравенства χ(G) ≤ λ(G) ≤ δ(G), где δ(G) — минимальная степень вершин графа G, а λ(G) — число рёберной связности, то есть наименьшее число рёбер, удаление которых приводит к несвязному графу. 3