Вопрос школьника
Докажите, что в любом графе сумма индексов всех его вершин — число чётное, равное удвоенному числу рёбер графа. Выведите из этого, что число вершин с нечётными индексами чётно.
Ответ от учителя
Для доказательства данного утверждения рассмотрим произвольный граф с $n$ вершинами и $m$ ребрами. Индекс вершины определяется как количество ребер, соединяющих данную вершину с остальными вершинами графа. Таким образом, сумма индексов всех вершин равна $2m$, так как каждое ребро соединяет две вершины и учитывается дважды.
Таким образом, сумма индексов всех вершин графа является четным числом, равным удвоенному числу ребер графа.
Теперь рассмотрим вершины графа с нечетными индексами. Предположим, что их количество нечетно. Тогда сумма индексов всех вершин графа будет нечетной, так как каждая нечетная вершина добавляет к сумме нечетное число. Но мы уже доказали, что сумма индексов всех вершин графа является четным числом, поэтому предположение о том, что количество вершин с нечетными индексами нечетно, неверно.
Следовательно, количество вершин с нечетными индексами является четным числом.
