В принципе теорема следует из принципа Дирихле (нельзя посадить n кроликов в n-1 клеток, чтобы в каждой клетке был один кролик). Но прямой чисто логический вывод ее из принципа Дирихле труден - есть работы логиков, показывающие, что такое доказательство должно быть длинным. Доказательство Бонди красиво использует элементарную теорию графов следующим образом.
Пусть есть матрица размером n на n, в которой все строки попарно отличаются. Скажем, что столбец i соединяет две строки, если при удалении этого столбца они становятся идентичными. Скажем, что столбец активен, если он соединяет хоть какую-то пару строк. Мы хотим доказать, что число активных столбцов меньше n. Если это так, то любой неактивный столбец можно удалить, и в оставшейся матрице все еще строки попарно отличаются.
Мы можем прыгать от строки к строке, пользуясь соединяющими столбцами, т.е. меняя каждый раз значение в одном столбце. Таким образом строки можно рассматривать как вершины графа: две вершины соединены ребром, если есть соединяющий их столбец. Все вершины распадаются на какое-то количество компонент связности. Вообще говоря один столбец может участвовать в большом количестве ребер между разными строками. Ясно, что в любом случае
(1) число активных столбцов меньше или равно числу ребер в графе.
Предположим, что в каждой компоненте связности нет циклов, т.е. нет возможности начать из одной строки и вернуться в нее же, не пользуясь дважды одним ребром. Тогда каждая компонента - дерево, а в дереве меньше ребер, чем вершин (на 1). Суммируя по всем компонентам, получаем, что во всем графе
(2) число ребер меньше числа вершин n.
Соединяя (1) и (2), получаем то, что мы хотели доказать.
Но может оказаться, что в каких-то компонентах есть циклы. Посмотрим на любой такой цикл. В нем мы путешествуем от строки к строке, ни разу не пользуясь одним и тем же ребром. Но несомненно нам придется пользоваться дважды одним *столбцом*. Например, если первым шагом мы меняем столбец i, то чтобы вернуться в исходную строку, нам рано или поздно опять придется поменять столбец i, хоть и между другими строками. Возьмем в любом цикле два таких ребра, принадлежащих одному столбцу, и одно из этих ребер выбросим из графа. Это разобьет цикл, но оставит число активных столбцов неизменным (потому что второе ребро того же столбца мы оставили). В новом графе (1) все еще верно, и число активных столбцов в нем то же, что и раньше. Будем продолжать так разбивать циклы, пока их не останется, после чего вышеприведенный аргумент заканчивает доказательство.
Update: красивое геометрическое доказательство
hyperpov в комментариях, не пропустите! 