Давайте докажем, что если числа и различны, то НОД. Пусть , тогда НОД, а 2НОД (так как делится на НОД, но равно быть не может, так как числа не равны и большее число, значит, 2НОД). Получили, что 3НОД. Давайте для каждого ребра запишем полученную оценку и сложим все неравенства, каждая вершина используется в трех неравенствах, поэтому сумма всех НОДов меньше либо равна суммы всех чисел. Предположим, что эти суммы равны, тогда равенство достигается в каждом неравенстве, выше. То есть равенство возможно только при или (для каждого ребра).

Не теряя общности пусть , но тогда: либо , тогда нашлись два равных числа, либо , но также или , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.