Лемма. Жадный алгоритм стоит независимое множество максимального веса.

Доказательство. Так как все веса положительные, то множество максимального веса будет базой матроида. Пусть B_G = {e₁, e₂, e₃, …, e_r}, причем выписаны они в том порядке, в каком алгоритм выбирал их. Тогда w(e₁) ≥ w(e₂) ≥ … ≥ w(e_r). Рассмотрим базу B = {f₁, f₂, f₃, …, f_r}, причем элементы тоже упорядочены по убыванию. Пусть она будет базой максимального веса. Далее будет доказано, что всегда будет выполняться неравенство w(e_k) ≥ w(f_k).

Будем доказывать от противного. Пусть k + 1 будет наименьшим индексом, для которого это соотношение не будет выполняться — w(e_k+1) < w(f_k+1). Рассмотрим два множества — Y = {e₁, e₂, e₃, …, e_k}, X = {f₁, f₂, f₃, …, f_k+1}. По третьему свойству матроидов Y  {f_i}  I для какого-то i  {1, 2, …, k + 1}. Но w(f_i) ≥ w(f_k+1) ≥ w(e_k+1). Но алгоритм должен был выбрать f_i в предпочтение e_k+1. Получили противоречие. Поэтому w(e_i) ≥ w(f_i). Так как было сделано предположение, что B — максимального веса, то из этого следует что алгоритм действительно строит независимое множество максимального веса.