100. Постройте граф, у которого число вершин на 3 меньше, чем число рёбер, и который имеет 8 циклов.

Для связного графа число независимых циклов равно

\(\mu=m-n+1\).

По условию \(m=n+3\), значит \(\mu=(n+3)-n+1=4\). Поэтому при стандартном понимании цикломатического числа условие «8 циклов» несовместимо с разностью, равной 3: для 8 независимых циклов должно быть \(m-n+1=8\), то есть \(m=n+7\).

Например, граф с 9 вершинами и 16 рёбрами имеет 8 независимых циклов: взять центральную вершину \(v_1\), соединить её с вершинами \(v_2,\ldots,v_9\), а также добавить рёбра \(v_2v_3,v_2v_4,\ldots,v_2v_9\). Тогда \(m=16\), \(n=9\), и

\(\mu=16-9+1=8\).

Ответ: в условии, вероятно, опечатка; для 8 циклов нужно, чтобы число рёбер было на 7 больше числа вершин.