Добрый день. Не могу понять задачу про сэра Гавса.

Сэр Гавс гоняется за сэром Мявсом по аллеям аккуратного английского парка, состоящего из площадок и соединяющих их дорожек. Сэр Гавс хочет загнать сэра Мявса в тупик и там цапнуть его за хвост. Но если сэр Мявс сумеет найти в парке путь, по которому можно бегать кругами (цикл), то сэр Гавс быстро выдохнется, и хвост сэра Мявса не пострадает. Известно, что если представить парк в виде графа, то он будет связным, с 13 вершинами и 13 рёбрами. Уцелеет ли хвост сэра Мявса?

Здравствуйте!

У нас связный неориентированный граф без петель и без кратных рёбер.
Если этот граф не имеет цикла, то у него должно быть `B-P=1`, где `B` - число вершин, а `P` - число рёбер графа. В нашей задаче `B-P=13-13=0 != 1`. Значит, граф не является деревом, то есть имеет как минимум один цикл. Хвост хвост сэра Мявса уцелеет.

Спасибо!