Вправи: 131

131. У регіоні країни є 8 міст. Чи можна стверджувати, що з будь–якого міста можна проїхати в будь–яке інше місто, якщо з кожного міста виходить: 1) не менше трьох доріг; 2) чотири дороги?

Позначимо 8 міст точками

За умовою з будь–якого міста можна проїхати з будь–яке інше місто. Якщо перейти на мову графів, то такий граф називається зв'язним.

1. Не менше трьох доріг N ≥ 3

Ні, бо як бачимо зліва, зображений варіант 2 прямокутників (8 вершин) і з кожної виходить 3 ребра, але між собою прямокутники не з'єднані, тому граф не є зв'язним.

2. Так. Візьмемо два міста і нехай між ними немає сполучення. Кожне з них з'єднані з іншими містами, тоді в регіоні як мінімум 10 міст.