Teoria grafów, problem ze znalezieniem ilości klik

Kulfon · Post autor: **Kulfon** » 3 mar 2013, o 14:27

Mam problem z poniższym zadaniem:
Jeżeli graf posiada 12 trójkątów, jaka jest największa ilość 4-wierzchołkowych klik które może posiadać?

W jaki sposób do tego pojdeść?

Errichto · Post autor: **Errichto** » 4 mar 2013, o 11:21

Zapewne trzeba tu się mocno rozpisać, eleganckiego rozwiązania nie ma. Musisz rozpatrzeć przypadek dwóch/trzech rozłącznych 4-wierzchołkowych klik (ile wtedy mamy trójkątów?), co gdy dwa 4-wierzchołkowce mają część wspólną, w szczególności gdy 3 wierzchołki są wspólne. A jak wtedy dorzucimy jeszcze jedną krawędź to mamy 5-klikę, która da \(\displaystyle{ {5 \choose 4}}\) żądanych 4-wierzchołkowych klik.
Dużo pisania i przypadków.