Граф товаришування
Граф товаришування (або граф данського млина, або n-лопатевий вентилятор) Fn — це планарний неорієнтований граф з 2n+1 вершинами і 3n ребрами[1].
Граф товаришування Fn можна побудувати, з'єднавши n копій циклів C3 в одній спільній вершиніШаблон:Sfn.
З побудови граф товаришування Fn ізоморфний вітряку Wd(3,n). Граф є графом одиничних відстаней, має обхват 3, діаметр 2 і радіус 1. Граф F2 ізоморфний метелику.
Теорема про граф товаришування
Теорема про граф товаришування Ердеша, Реньї і ШошШаблон:SfnШаблон:Sfn стверджує, що скінченні графи з властивістю, що будь-які дві вершини мають рівно одного спільного сусіда, це в точно графи товаришування. Неформально, якщо група людей має властивість, що будь-яка пара людей має рівно одного спільного друга, то має бути одна особа, яка є другом решти членів групи. Для нескінченних графів, однак, може існувати багато різних графів однакової потужності, що мають цю властивістьШаблон:Sfn.
Комбінаторне доведення теореми про граф товаришування дали Мертціос і УнгерШаблон:Sfn. Інше доведення дав Крейг ХунекеШаблон:Sfn.
Розмітка і розфарбування
Граф товаришування має хроматичне число 3 і хроматичний Індекс 2n. Його хроматичний многочлен можна отримати з хроматичного многочлена циклу C3, він дорівнює .
Граф товаришування Fn має досконалу розмітку ребер тоді і тільки тоді, коли n непарне. Він має граціозну розмітку тоді і тільки тоді, коли n ≡ 0 (mod 4), або n ≡ 1 (mod 4)Шаблон:SfnШаблон:Sfn.
Будь-який граф товаришування є фактор-критичним.
Екстремальна теорія графів
Згідно з екстремальною теорією графів будь-який граф з досить великим числом ребер (відносно числа вершин) повинен містити, як підграф, k-лопатевий вітряк. Точніше, це істинне для графа з n вершинами, якщо число ребер дорівнює
де f(k) дорівнює k2 − k, якщо k непарне, і f(k) дорівнює k2 − 3k/2, якщо k парне. Ці межі узагальнюють теорему Турана про число ребер у графі без трикутників і вони є кращими межами для цієї задачі, оскільки для будь-якого меншого числа ребер існують графи, що не містять k-лопатевого вітрякаШаблон:Sfn.