MathCastle
Graph TheoryHardEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Hard problem

A graph has a clique on {1,2,3,4,5}\{1,2,3,4,5\} (all 1010 edges present), plus vertex 66 joined to 3,4,53,4,5, plus vertex 77 joined to 1,2,41,2,4 (77 vertices total). Among all non-adjacent pairs, find the smallest value of deg⁡(u)+deg⁡(v)\deg(u)+\deg(v), and state whether Ore's theorem guarantees a Hamiltonian cycle here.