Возьмём какие-то две вершины, между которыми ровно 2 простых пути, и эти этом пути не пересекаются по рёбрам. Эти две вершины лежат на каком-то цикле. (Если не на цикле, то начала или концы путей совпадут, либо путей будет меньше 2.)

Пример: в обоих графах между двумя красными вершинами 2 простых пути, но в правом графе они имеют общее ребро, что нам не подходит.

Если этот их общий цикл пересекается с другим циклом по ребру, то путей будет больше двух (так как в одном из двух наших путей есть это ребро, и можно либо пройти либо по нему, либо по циклу). Значит, такого не должно быть.

Пример: между двумя красными вершинами больше двух путей, так как их цикл пересекается с другим циклом.

Заметим, что тогда условие выполняется и для всех других пар вершин на нашем цикле. Значит, нам выгодно делать в нашем графе много простых циклов. Но эти циклы могут пересекаться в одной вершине, мы запрещали только пересечения по ребру.

А также отметим, что если уже выполнили необходимое условие (набрали $$$k$$$ пар), использовав некоторое количество вершин, то из остальных вершин можем не проводить рёбер, это ничего не нарушит. То есть нам хочется использовать как можно меньше вершин для достижения цели.

Тогда оптимальный граф выглядит как «дерево» из циклов, соединенных между собой в одной вершине. Заметим, что в таком графе между вершинами разных циклов больше двух различных простых путей.

Пример «дерева» из циклов.

В цикле длины $$$d$$$ всего $$$\frac{d(d-1)}{2}$$$ пар вершин, и они все подходят под наше условие. Будем решать задачу с помощью динамического программирования. Пусть $$$dp[i]$$$ — минимальное количество вершин, с помощью которых можно сделать $$$i$$$ пар вершин, подходящих под наше условие. Пересчёт: $$$dp[i + \frac{d * (d - 1)}{2}] = min(dp[i + d * (d - 1) / 2], dp[i] + d - 1)$$$. Не забываем вычитать единицу, так как наши циклы соединены. Асимптотика $$$O(k\sqrt{k})$$$ (так как количество пар вершин в цикле растёт квадратично). Если $$$dp[k] \leq n$$$, то можно сделать такой граф. Оставшиеся вершины просто оставим без рёбер.