Доказательство этих утверждений является довольно сложным, но может быть выполнено путем анализа отдельных случаев: если действия А и В являются взаимно исключающими на уровне Аi, то должны быть таковыми из-за наличия одного из трех типов взаимно исключающих связей. Первые два из них, несогласованные результаты и вмешательство, обусловлены свойствами самих действий, поэтому, если действия являются взаимно исключающими на уровне Ai, то будут взаимно исключающими на каждом уровне. Третий случай, с конкурирующими потребностями, зависит от условий на уровне Si . этот уровень должен содержать предусловие действия A, которое является взаимно исключающим по отношению к предусловию действия в. Теперь отметим, что эти два предусловия могут быть взаимно исключающими, если они являются отрицаниями друг друга (и в этом случае они будут взаимно исключающими на каждом уровне) или все действия по достижении одного из них являются взаимно исключающими по отношению ко всем действиям, необходимым для достижения другого. Но мы уже знаем, что количество допустимых действий увеличивается монотонно, поэтому по индукции количество взаимно исключающих связей должно уменьшаться.

Поскольку количество действий и литералов увеличивается, а количество взаимно исключающих связей уменьшается, и поскольку имеется только конечное количество действий и литералов, каждый граф планирования в конечном итоге выравнивается — все последующие уровни в нем становятся идентичными. После того как граф выровнялся, он может быть проанализирован, и если в нем отсутствует одна из целей задачи или две цели являются взаимно исключающими, то данная задача никогда не может быть решена, поэтому мы можем остановить работу алгоритма Graphplan и вернуть индикатор неудачи. Если же граф выравнивается со всеми присутствующими и не взаимно исключающими целями, но функция Extract-Solution оказывается не в состоянии найти решения, то может потребоваться снова расширить граф конечное количество раз, но так или иначе мы имеем возможность остановить работу алгоритма. Последний вариант завершения является более сложным и здесь не рассматривается.