Grafo hamiltoniano

Um grafo é dito hamiltoniano se e somente se ele possui um ciclo hamiltoniano.

Um ciclo hamiltoniano em um grafo $G$ é um ciclo que engloba todos os vértices de $G$.

Uma condição suficiente (porém não necessária) para um grafo $G=(V,A)$ ser hamiltoniano é que $|V|\ge 3$ e que cada vértice tenha grau pelo menos $\frac{|V|}{2}$.