Input: G = (V, E): graph with n vertices and m edges Input: n, m: order and size of G Output: whether G has a Hamiltonian Path 1 Algorithm: HamiltonianReduction 2 if HC(G) then sreturn true end 5 for i = 1 to n-1 do for j = i + 1 to n do if not G.isAdjacent(i, j) then G.AddEdge(i, j) if HC(G) then 10 return true end G.RemoveEdge(i, j) 12 13 14 end 15 end 16 return false end