Связность и связные подграфы (клики)

Примером служит объединение двух графов или куб.

Оценка. Если граф дружб несвязный, то рассмотрим две вершины и из одной компоненты связности и одну из другой. В этой тройке пара обязана быть общительной, значит, есть вершины и связанные каждая с и Рассмотрим тройку Общительной должна быть пара Двух новых общих друзей у них быть не может, т.к. степени вершин и стали бы равны Значит, одним из общих знакомых является (или что из симметрии всё равно). Второй их общий знакомый тоже не может быть новым, т.к. степень вершины стала бы больше Значит, второй общий знакомый у и — это Итак, вершины образуют граф и это одна из компонент связности Взяв одну вершины из этой компоненты, а две — из другой, мы аналогичными утверждениями придём к существованию ещё одной компоненты связности графа — тоже Таким образом, мы построили граф с вершинами (две компоненты Трёх компонент связности в быть не может, т.к. из трёх вершин, взятых из разных компонент, общительных пар образоваться не может.

Пусть граф дружб связен. Найдем общительную пару. Она порождает квадрат где ребра идут по циклу. Заметим, что никакая из сторон квадрата не может быть общительной парой, иначе в квадрате все друг с другом знакомы, и квадрат образует отдельную компоненту связности. В частности, вершины общительной пары должны быть не знакомы. У вершин квадрата есть еще не более знакомых. Допустим, в графе более вершин. По лемме о рукопожатиях их число четно, значит, вершин не менее Выберем две вершины, не связанные с квадратом, и еще одну, не входящую в квадрат. Среди них есть общительная пара, которая порождает еще один квадрат Он не пересекается с первым, иначе общая вершина имела бы степень Найдется вершина не входящая в эти квадраты, но связанная ребром с одним из них, например, с вершиной Рассмотрим тройку Общительной пара — это или что все равно. Пусть это Тогда у есть с общий знакомы во втором квадрате, пусть это Рассмотрим тройку Не знакомы только и но пара не общительная, так как у нее ровно один общий знакомый — это Противоречие.