Алгоритм Гавела — Хакими — рекурсивный алгоритм позволяющий определить появляется ли данный список целых чисел как список всех валентностей некоторого конечного простого графа. При положительном ответе на этот вопрос список называется графическим.
Пусть <math>s,d_1,\dots,d_s,t_1,\dots,t_k</math> есть конечный список неотрицательных целых чисел в невозрастающем порядке.
Список <math>s,d_1,\dots,d_s,t_1,\dots,t_k</math> является графическим, тогда, и только тогда, когда список <math>d_1-1,\dots,d_s-1,t_1,\dots,t_k</math> графический.
Описанную операцию следует применять поочерёдно с упорядочиванием списка.
Если в какой-то момент получаем список из нулей то изначальный список являлся графическим.
Если же в списке появится отрицательное число то изначальный список не являлся графическим.
Применим алгоритм к списку <math>4,4,3,3,2,2,1,1</math>. Мы поочерёдно применяем теорему и упорядочивание. То что в результате получается список из нулей означает, что список <math>4,4,3,3,2,2,1,1</math> графический.
Применим алгоритма к списку <math>7,6,3,3,2,2,1,1</math>. То что в результате получается список из отрицательных чисел означает, что список <math>7,6,3,3,2,2,1,1</math> не является графическим.
