Гамильтонов цикл в неориентированном графе и генератор неориентированных графов

Задание :Гамильтонов цикл в графе G = (V, E) – это цикл в графе G, содержащий все вершины из V. Найти гамильтонов цикл в заданном неориентированном графе. Исследовать асимптотическую временную сложность решения задачи в зависимости от размеров (числа вершин и числа ребер) исходного графа. У меня вопрос я написал код и при введении минимального числа ребер не находит гамильтонов цикл как улучшить генератор графов?

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm>
#include <chrono>

using namespace std;
using namespace std::chrono;

// Генерация случайного неориентированного графа
vector<vector<int>> generateGraph(int V, int E) {
vector<vector<int>> graph(V, vector<int>(V, 0));
srand(time(0));
while (E > 0) {
int u = rand() % V;
int v = rand() % V;
if (u != v && graph[u][v] == 0) {
graph[u][v] = graph[v][u] = 1;
E--;
}
}
return graph;
}

// Проверка, можно ли добавить вершину в путь
bool isSafe(int v, int pos, vector<int> &path, vector<vector<int>> &graph) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}

// Рекурсивная функция для нахождения Гамильтонова цикла с помощью backtracking
bool hamiltonianCycleUtil(vector<vector<int>> &graph, vector<int> &path, int pos) {
if (pos == graph.size()) {
if (graph[path[pos - 1]][path[0]] == 1)
return true;
else
return false;
}

for (int v = 1; v < graph.size(); v++) {
if (isSafe(v, pos, path, graph)) {
path[pos] = v;
if (hamiltonianCycleUtil(graph, path, pos + 1) == true)
return true;
path[pos] = -1;
}
}
return false;
}

bool findHamiltonianCycle(vector<vector<int>> &graph) {
vector<int> path(graph.size(), -1);
path[0] = 0;
return hamiltonianCycleUtil(graph, path, 1);
}
int main() {
    vector<int> sizes = {10, 12, 15, 20};
    cout << "Размер графа\tКол-во ребер\tСреднее время (μs)" << endl;

    for (int V : sizes) {
        vector<int> edgeCounts = {(V * (V - 1)) / 4 + 1 , (V * (V - 1)) / 2};

        for (int E : edgeCounts) {
            double totalDuration = 0;
            int successfulAttempts = 0;

            for (int i = 0; i < 100000; i++) {
                vector<vector<int>> graph = generateGraph(V, E);
                auto start = high_resolution_clock::now();
                if (findHamiltonianCycle(graph)) {
                    auto end = high_resolution_clock::now();
                    auto duration = duration_cast<microseconds>(end - start).count();
                    totalDuration += duration;
                    successfulAttempts++;
                }
            }

            if (successfulAttempts > 0) {
                double averageDuration = totalDuration / successfulAttempts;
                cout << V << "\t\t" << E << "\t\t" << averageDuration << endl;
            } 
        }
    }

    return 0;
}