Cuckooo Cycle Question

[eca20]

When the difficulty is set for a cycle, is there any background sorcery in the code that guarantees that there would be a solution? If you have it set to a high number, and the pseudorandom graph does not have a cycle that large, what goes down?

[eca20]

A more refined question would be: is it possible to prove, with relative ease, that there exists an answer to the puzzle (whether it is a cuckoo cycle, or the hash puzzle bitcoin uses), while not being able to find the/a solution with the same ease.