Treść zadania jest następująca:
Ile jest grafów o polu 9-elementowym. Ile z nich jest takich, że zawiera podgraf zupełny o polu 5-elementowym i ich dopełnienie też zawiera podgraf zupełny o polu 5-elementowym.
Zatrzymuję się na pierwszej części zadania:
"Ile jest grafów o polu 9-elementowym."
Problem w tym, że wierzchołki są nieoznaczone. Gdyby wierzchołki tego grafu były oznaczone, łatwo byłoby policzyć ilość takich grafów:
Najpierw liczymy liczbę wszystkich możliwych krawędzi między dowolnymi dwoma punktami
\(\displaystyle{ {9 \choose 2}}\)
Później znajdujemy liczbę wszystkich grafów 9-elementowych czyli liczbę podzbiorów zbioru wyliczonej wcześniej liczby krawędzi
\(\displaystyle{ 2 ^{ {9 \choose 2} }}\)
Wygląda na to, że liczba grafów o nieoznaczonych wierzchołkach jest o wiele mniejsza niż grafów o wierzchołkach oznaczonych. Niestety nie wiem w jaki sposób policzyć tą liczbę.
Będę wdzięczny za każdą pomoc.