Изобразите связный граф с семью вершинами, который имеет цикл, длина которого…

Условие ученика: в цикле совпадают только первая и последняя вершины, то есть остальные вершины не повторяются.

Цикл длины состоит из рёбер и проходит через вершин (первая и последняя — одна и та же). Значит, в нём различных вершин.

В графе всего вершин, поэтому при таком условии цикл длиной построить нельзя. Самый длинный такой цикл в графе с вершинами имеет длину .

Если разрешить повторять вершины (в задачнике «цикл» может быть замкнутым маршрутом), задача решается.

Граф: вершины –, рёбра –, –, –, –, –, –, –, –, –. Он связный, так как все вершины соединены с вершиной .

Цикл:

Он состоит из рёбер: . Вершина повторяется несколько раз.