Алгебра
Английский
Биология
География
Геометрия
История
Русский
Обществознание
Физика
Химия
Информатика
Литература
МатематикаВопрос:
На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?
Ответ:
Нет, это невозможно, так как сумма степеней вершин должна быть чётной.
Похожие
- На рисунке 19, 8 (с. 81) изображён граф. Сколько у каждого из них вершин степени 0, степени 1 и степени 2?
- Существует ли граф, в котором 5 вершин, и они имеют степени 1, 2, 2, 3, 3?
- Придумайте и нарисуйте два неоднонаковых графа, в каждом из которых по 5 вершин со степенями 1, 1, 2, 2, 3, 3.
- Может ли количество вершин нечётной степени в каком-нибудь графе равняться: а) 0; б) 2; в) 3; г) 4?
- Придумайте и нарисуйте 3 неоднонаковых графа, в каждом из которых по 6 вершин. Найдите сумму степеней вершин для каждого из этих графов.
- Докажите, что сумма степеней всех вершин вдвое больше числа рёбер в этом графе.
- В некотором графе 6 вершин, степени которых равны: а) 2, 2, 3, 3, 4, 4; б) 0, 1, 1, 2, 2, 3, 4. Сколько всего рёбер в этом графе?
