Graph TheoryHardEulerian and Hamiltonian Graphs
Eulerian and Hamiltonian Graphs · Hard problem
A graph has a clique on (all edges present), plus vertex joined to , plus vertex joined to ( vertices total). Among all non-adjacent pairs, find the smallest value of , and state whether Ore's theorem guarantees a Hamiltonian cycle here.