Рас­смот­рим об­щи­тель­ное мно­же­ство A наи­мень­ше­го раз­ме­ра. За­ме­тим, что можно вы­брать A таким, что для каж­до­го тро­гло­ди­та a из A най­дет­ся тро­гло­дит v_a, един­ствен­ный друг ко­то­ро­го в мно­же­стве A  — тро­гло­дит a. Дей­стви­тель­но, в про­тив­ном слу­чае, если a дру­жит с кем-то из A, то его можно про­сто уда­лить, а если не дру­жит ни с кем из A, то её можно по­ме­нять с любым его дру­гом.

Пусть в A най­дут­ся дру­зья, ска­жем, a и b. Тогда все тро­гло­ди­ты, для ко­то­рых един­ствен­ный друг в мно­же­стве A  — тро­гло­дит a, дру­жат между собой. В самом деле, пусть v_a и ua не дру­жат, тогда a, b, v_a и ua про­ти­во­ре­чат усло­вию. Таким об­ра­зом, можно за­ме­нить a на v_a, мно­же­ство A оста­нет­ся об­щи­тель­ным, а число пар дру­жа­щих тро­гло­ди­тов в A умень­шит­ся.

По­вто­рив опи­сан­ные рас­суж­де­ния не­сколь­ко раз по­лу­чим стран­ное об­щи­тель­ное мно­же­ство раз­ме­ра не боль­ше, чем было ис­ход­но.