Страница 111 номер 161, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 1 часть. Углубленный уровень
На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?
Каждый учёный — вершина, ребро соединяет двух знакомых между собой учёных; степень вершины равна числу знакомых учёного.
У пяти вершин степень 3 — нечётная. У всех остальных вершин степень 4 — чётная. Значит, вершин нечётной степени в графе знакомств было бы ровно пять. Но в любом графе количество вершин нечётной степени чётно, поэтому так оказаться не могло.
Ответ: нет: в графе знакомств было бы пять вершин нечётной степени.
На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?
Сопоставим каждому учёному вершину; ребро соединяет двух знакомых между собой учёных. Тогда степень вершины равна числу знакомых учёного.
Пятеро учёных знакомы ровно с тремя другими — у пяти вершин степень 3, нечётная. У всех остальных вершин степень 4 — чётная. Значит, вершин нечётной степени в графе знакомств было бы ровно пять. Но в любом графе количество вершин нечётной степени чётно, поэтому так оказаться не могло.
Ответ: нет: в графе знакомств было бы пять вершин нечётной степени.
