Задание 12. Постройте граф, который не является связным, таким образом, чтобы при добавлении одного ребра он стал связным.

Построим граф из двух компонент: первая компонента содержит вершины A, B, C и рёбра AB, BC; вторая — вершины D, E и ребро DE. Добавим ребро CD.

Пунктиром показано добавляемое ребро CD. После его добавления между двумя компонентами появляется связь, поэтому граф становится связным.

Ответ: можно добавить ребро CD.