Naším cílem je zjistit, kolik různých neorientovaných grafů může existovat na daném počtu vrcholů, který označíme jako n.

Nejprve si ujasněme, co definuje graf. Graf je tvořen množinou vrcholů a množinou hran, které tyto vrcholy spojují. Pro náš případ uvažujeme n pevných, rozlišitelných vrcholů. Dva grafy se liší, pokud mají odlišnou množinu hran.

Klíčová otázka tedy zní: kolik je všech možných hran, které mohou v grafu s n vrcholy existovat? Hrana v neorientovaném grafu je definována jako neuspořádaná dvojice různých vrcholů. To je klasická kombinatorická úloha: kolika způsoby můžeme vybrat 2 vrcholy z celkového počtu n?

Počet takových dvojic je dán kombinačním číslem "n nad 2": \[\binom{n}{2} = \frac{n(n-1)}{2}\] Tento výraz nám udává maximální počet hran v grafu o n vrcholech (tzv. úplný graf).

Nyní pro každou z těchto potentiálních hran máme dvě možnosti: buď v konkrétním grafu existuje, nebo neexistuje. Jelikož máme \(\binom{n}{2}\) nezávislých hran a pro každou z nich 2 možnosti, celkový počet kombinací (a tedy různých grafů) získáme použitím pravidla součinu.

Výsledný vzorec pro počet neorientovaných grafů na n vrcholech je: \[N_G = 2^{\binom{n}{2}} = 2^{\frac{n(n-1)}{2}}\]

Důkaz si můžeme představit pomocí jednoduché myšlenkové úvahy.

1. Představme si všechny možné hrany: Máme n vrcholů. Jak jsme si ukázali v předchozí kapitole, maximální počet hran, které mezi nimi mohou vést, je přesně \(\binom{n}{2}\). Můžeme si představit seznam všech těchto \(\binom{n}{2}\) potenciálních hran.
2. Rozhodnutí pro každou hranu: Nyní, když chceme vytvořit nějaký konkrétní graf, musíme pro každou jednu hranu z tohoto seznamu učinit jednoduché rozhodnutí: Bude tato hrana v našem grafu, nebo ne? Máme tedy pro ni dvě možnosti: ANO, nebo NE.
3. Nezávislé volby: Rozhodnutí pro jednu hranu nijak neovlivňuje rozhodnutí pro jakoukoliv jinou hranu. Jsou to nezávislé volby.
4. Pravidlo součinu: Máme \(\binom{n}{2}\) pozic (potenciálních hran) a pro každou z nich máme 2 možnosti. Podle základního kombinatorického pravidla součinu je celkový počet možností roven součinu počtu voleb pro každou pozici.
5. Výpočet: Celkový počet kombinací je tedy \(2 \times 2 \times 2 \times \dots \times 2\), kde dvojku násobíme celkem \(\binom{n}{2}\)-krát.
6. To je z definice mocniny rovno \(2^{\binom{n}{2}}\). Každá tato unikátní kombinace voleb "ANO/NE" odpovídá jednomu unikátnímu grafu. Tím je vzorec dokázán.

Zajímá nás, jak rychle roste počet grafů v závislosti na počtu vrcholů n, když se n blíží k nekonečnu. K tomu používáme O-notaci.

Náš vzorec je \(f(n) = 2^{\frac{n(n-1)}{2}} = 2^{\frac{n^2 - n}{2}}\).

Pro velká n je člen \(n^2\) v exponentu dominantní a člen \(-n\) je zanedbatelný. Můžeme tedy říci, že funkce roste zhruba jako \(2^{\frac{n^2}{2}}\).

V O-notaci zanedbáváme konstantní faktory v exponentu (v tomto případě \(1/2\)). Asymptotickou složitost tedy můžeme zapsat jako: \[O\left(2^{n^2}\right)\]

Jedná se o dvojitě exponenciální růst vzhledem k základu a exponenciální vzhledem k n, ale s \(n^2\) v exponentu. Růst je tedy extrémně rychlý, což je patrné i z hodnot v tabulce. Počet možných grafů se s každým přidaným vrcholem dramaticky zvyšuje.