Вправи: 972

972. У країні є 15 міст, кожне з яких сполучене дорогою принаймні із 7 іншими. Доведіть, що дорогами країни можна проїхати з будь-якого міста до будь-якого іншого міста.

Припустимо, що знайдуться два міста А і В такі, що дорогами країни

проїхати з А в В неможливо. За умовою кожне з міст A i B сполучено

дорогою принаймні із 7 іншими містами. Оскільки інших міст є 13,

то серед них знайдеться місто С, яке сполучено дорогою і з містом А,

і з містом В.