Рас­смот­рим граф зна­комств ма­те­ма­ти­ков. По усло­вию этот граф хор­до­вий, т. е. в нем любой цикл из 4 или более вер­шин со­дер­жит хорду (пару смеж­ных вер­шин, не со­сед­них в цикле). До­ка­жем, что для хор­до­во­го графа G вы­ра­же­ние

где   — ко­ли­че­ство клик в G на i вер­ши­нах, равно числу ком­по­нент связ­но­сти графа G.

Ре­ше­ние 1. Пред­по­ло­жим, что это не так, и рас­смот­рим в ка­че­стве G наи­мень­ший по числу вер­шин контр­при­мер. Ясно, что граф G со­дер­жит боль­ше одной вер­ши­ны и свя­зен (иначе одна из ком­по­нент связ­но­сти была бы мень­шим контр­при­ме­ром). Уда­лим из графе G про­из­воль­ную вер­ши­ну υ, пусть новый граф рас­пал­ся на ком­по­нен­ты Пусть   — под­гра­фы в со­от­вет­ствен­но на со­се­дях вер­ши­ны υ. Не­слож­но ви­деть, что

где сла­га­е­мое 1 со­от­вет­ству­ет клике сла­га­е­мые   — кли­кам, не со­дер­жа­щим υ, сла­га­е­мые  —   — кли­кам, со­дер­жа­щим υ (при уда­ле­нии из них вер­ши­ны υ ме­ня­ет­ся чет­ность, а стало быть, знак в вы­ра­же­нии для f). В силу ми­ни­маль­но­сти контр­при­ме­ра Про­ве­рим, что при всех i. Пред­по­ло­жим про­тив­ное, тогда вер­ши­ны од­но­го из гра­фов можно раз­бить на два не­пу­стых под­мно­же­ства так, что ни одно ребро не ведет из в Рас­смот­рим наи­мень­ший по числу ребер путь из в в графе Тогда цикл не имеет хорды в графе Мы про­ве­ри­ли, что при всех i. Тогда по фор­му­ле (*) т. е. граф G ока­зал­ся не контр­при­ме­ром.

Ре­ше­ние 2. На­зо­вем вер­ши­ну до­пу­сти­мой, если все ее со­се­ди по­пар­но смеж­ны­ми между собой.

Лемма. В хор­до­вом графе, име­ю­щем хотя бы две вер­ши­ны, есть хотя бы две до­пу­сти­мые вер­ши­ны.

До­ка­за­тель­ство. Пред­по­ло­жив про­тив­ное, рас­смот­рим наи­мень­ший по числу вер­шин контр­при­мер  — граф G. За­ме­тим, что в G нет вер­ши­ны υ, смеж­ной со всеми (иначе   — мень­ший контр­при­мер). Пусть υ — не­до­пу­сти­мая вер­ши­на в G, N  — мно­же­ство со­се­дей вер­ши­ны υ,   — граф на остав­ших­ся вер­ши­нах. За­ме­тим, что если   — не­смеж­ные со­се­ди υ, то не су­ще­ству­ет пути из в все про­ме­жу­точ­ные вер­ши­ны ко­то­ро­го при­над­ле­жат H,  — иначе бы наи­мень­ший по числу ребер по­доб­ный путь, до­пол­нен­ный путем ока­зал­ся бы цик­лом без хорд. Пусть   — одна из ком­по­нент связ­но­сти графа мно­же­ство вер­шин в N, име­ю­щих со­се­да в По до­ка­зан­но­му   — клика, так что Рас­смот­рим (хор­до­вый, ра­зу­ме­ет­ся) граф на вер­ши­нах υ, В нем в силу ми­ни­маль­но­сти контр­при­ме­ра име­ет­ся до­пу­сти­мая вер­ши­на w, от­лич­ная от υ. Она не может при­над­ле­жать по­то­му что каж­дая вер­ши­на в имеет со­се­дя­ми υ и какую-то вер­ши­ну в Зна­чит, она при­над­ле­жит а по­то­му яв­ля­ет­ся до­пу­сти­мой и в G. Чтобы найти до­пу­сти­мую вер­ши­ну, от­лич­ную от w, по­вто­рим рас­суж­де­ние, взяв в ка­че­стве ис­ход­ной вер­ши­ны υ со­се­да вер­ши­ны w.

Воз­вра­ща­ясь к ре­ше­нию за­да­чи, будем рас­суж­дать по ин­дук­ции по числу вер­шин. Для до­пу­сти­мой вер­ши­ны υ ин­дук­ци­он­ный пе­ре­ход от графа к графу G очень про­стой: если она изо­ли­ро­ван­ная, ин­те­ре­су­ю­щая нас сумма уве­ли­чи­ва­ет­ся на 1, в про­тив­ном слу­чае ни сумма, ни число ком­по­нент связ­но­сти не ме­ня­ют­ся.