Почему в теории графов важно знать четность степени вершин?

В теории графов важно знать чётность степени вершин, потому что это позволяет применять одну из основных теорем: любой граф содержит чётное число нечётных вершин. urok.1sept.ru

Доказательство: количество рёбер графа равно половине суммы степеней его вершин. urok.1sept.ru Так как количество рёбер должно быть целым числом, то сумма степеней вершин должна быть чётной. urok.1sept.ru А это возможно только в том случае, если граф содержит чётное число нечётных вершин. urok.1sept.ru

Также следствие из этой теоремы позволяет определять, существует ли граф, если известно только количество нечётных вершин в графе. www.yaklass.ru

Кроме того, подсчитывая степени вершин, часто можно доказать, что два графа не являются одинаковыми. videouroki.net Например, если у одного из них есть вершина, степень которой равна 3, а у другого такой вершины нет. videouroki.net