137 Изобразите два графа с шестью вершинами степени 2: один связный, а другой нет.

Решение:

а) Связный граф с шестью вершинами степени 2.

б) Несвязный граф с шестью вершинами степени 2.

а) Связный граф: цикл из 6 вершин (например, шестиугольник). Каждая вершина имеет степень 2.

б) Несвязный граф: два несвязных компонента. Один компонент — цикл из 4 вершин, другой — цикл из 2 вершин (кратное ребро, если разрешено, или две вершины, соединенные двумя ребрами). Если кратные ребра запрещены, то два отдельных цикла: один из 4 вершин, другой из 2 вершин. Если графы простые, то можно два несвязных цикла: один из 4 вершин, другой из 2 вершин. Для простого графа: один цикл из 4 вершин, и второй цикл из 2 вершин.