§ 1. Лінійне рівняння з однією змінною » 131

У регіоні країни є 8 міст. Чи можна стверджувати, що з будь–якого міста можна проїхати в будь–яке інше місто, якщо з кожного міста виходить: 1) не менше трьох доріг; 2) чотири дороги? Позначимо 8 міст точками За умовою з будь–якого міста можна проїхати з будь–яке інше місто. Якщо перейти на мову графів, то такий граф називається зв'язним. 1. Не менше трьох доріг N ≥ 3 Ні, бо як бачимо зліва, зображений варіант 2 прямокутників (8 вершин) і з кожної виходить 3 ребра, але між собою прямокутники не з'єднані, тому граф не є зв'язним. 2. Так. Візьмемо два міста і нехай між ними немає сполучення. Кожне з них з'єднані з іншими містами, тоді в регіоні як мінімум 10 міст.