ГДЗ по вероятность и статистика 7-9 класс Высоцкий, номер 127

№

Граф знакомств

На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Решение

Изобразим каждого участника вершиной. Соединим двух участников ребром тогда и только тогда, когда они знакомы. По определению степени вершины из § она равна числу знакомых данного участника среди собравшихся.

У пятерых участников степень — нечётная. У каждого из остальных степень — чётная. Следовательно, в таком графе было бы ровно пять вершин нечётной степени. Но свойство из § утверждает, что число вершин нечётной степени всегда чётно: каждое знакомство даёт по единице к степеням двух участников. Пять — нечётное число, поэтому описанная ситуация невозможна.

Ответ

Нет, потому что ровно пять вершин нечётной степени в графе быть не может.

Помогло?

Номер 127