На­ри­су­ем схему: пла­не­та­ми будут со­от­вет­ство­вать точки, а со­еди­ня­ю­щим их марш­ру­там  — не­пе­ре­се­ка­ю­щи­е­ся между собой линии (см. рис.). Те­перь видно, что до­ле­теть от Земли до Марса нель­зя.

Ответ: 0.

Пред­по­ло­жим, что это воз­мож­но. Рас­смот­рим тогда граф, вер­ши­ны ко­то­ро­го со­от­вет­ству­ют те­ле­фо­нам, а ребра  — со­еди­ня­ю­щим их про­во­дам. В этом графе 15 вер­шин, сте­пень каж­дой из ко­то­рых равна пяти. Под­счи­та­ем ко­ли­че­ство ребер в этом графе. Для этого сна­ча­ла про­сум­ми­ру­ем сте­пе­ни всех его вер­шин. Ясно, что при таком под­сче­те каж­дое ребро учте­но два­жды (оно ведь со­еди­ня­ет две вер­ши­ны). По­это­му число ребер графа долж­но быть равно Но это число не­це­лое! Сле­до­ва­тель­но, та­ко­го графа не су­ще­ству­ет, а зна­чит, и со­еди­нить те­ле­фо­ны тре­бу­е­мым об­ра­зом не­воз­мож­но.

Пред­по­ло­жим, что есть два го­ро­да, между ко­то­ры­ми нет пути. Каж­дый из этих двух го­ро­дов по усло­вию со­еди­нен не менее, чем с семью дру­ги­ми го­ро­да­ми, при этом все эти го­ро­да раз­лич­ны  — ведь если какие-то два из них сов­па­да­ют, то су­ще­ству­ет путь, со­еди­ня­ю­щий ис­ход­ные го­ро­да (см. рис.). Но тогда в стра­не се­мер­ка не менее 16 го­ро­дов, что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, наше пред­по­ло­же­ние не­вер­но, и любые два го­ро­да свя­зы­ва­ет какой-то путь.

Пред­по­ло­жим, из сто­ли­цы не­воз­мож­но до­брать­ся до го­ро­да Даль­ний. Рас­смот­рим граф, вер­ши­на­ми ко­тор­го яв­ля­ют­ся все го­ро­да, кроме го­ро­да Даль­ний, а реб­ра­ми  — ков­ро­ли­нии, со­еди­ня­ю­щие эти го­ро­да между собой. В этом графе из одной вер­ши­ны (сто­ли­цы) вы­хо­дит 21 ребро, а из всех осталь­ных вер­шин  — по 20 ребер. Таким об­ра­зом, в этом графе ровно одна не­чет­ная вер­ши­на. Но это не­воз­мож­но, ведь в любом графе сумма сте­пе­ней всех вер­шин равна удво­ен­но­му числу ребер, по­это­му сумма сте­пе­ней всех вер­шин четна.

Ответ: 1.