Nell'ambito della matematica combinatoria, l'enumerazione di grafi descrive una classe di problemi di enumerazione combinatoria, nei quali un grafo diretto oppure indiretto è oggetto di calcolo algebrico, tipicamente in funzione del numero di vertici del grafo stesso.^[1] I problemi di questa classe ammettono sia una soluzione esatta come quelli di enumerazione algebrica, che una soluzione approssimata asintoticamente.

I pionieri in questo campo della matematica discreta furono Pólya^[2], Arthur Cayley^[3] e John Howard Redfield.^[4]

I vertici possono essere etichettati (in inglese: labeled) ovvero non etichettati (unlabeled). Nel primo caso, i vertici sono distinguibili l'uno dall'altro; nel secondo caso, invece, qualsiasi permutazione dei vertici forma il medesimo grafo e pertanto i vertici si dicono indisitnguibili ed equivalenti tra loro.

Il teorema di enumerazione di Pólya, noto anche come teorema di Redfield–Pólya, è un importante strumento analitico per ricondurre i problemi unlabeled alla più semplice forma di quelli labeled^[5], considerando ogni classe senza etichetta come una classe di simmetria di oggetti etichettati.

Alcuni risultati teorici di particolare rilievo sono dati dalle seguenti formule esatteò.

• il numero di grafi semplici indiretti etichettati che sono generati da un grafo di n vertici, è pari a 2^{n(n − 1)/2}.^[6];
• il numero di grafi semplici diretti etichettati che sono generati da un grafo di n vertici, è pari a 2^n(n − 1).^[7];
• il numero C_n di grafi connessi indiretti etichettati soddisfa la relazione di ricorrenza^[8]:

${\displaystyle C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.}$, che per n = 1, 2, 3,... restituisce i valori di C_n: 1, 1, 4, 38, 728, 26704, 1866256,... descritti dalla sequenza A001187 nel progetto OEIS;

• il numero di grafi ad albero liberi etichettati che sono generati da un grafo di n vertici, è pari a n^n − 2(formula di Cayley);
• il numero di grafi a bruco, che sono generati da un grafo di n vertici, è pari a^[9]:

${\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}$

Portale Matematica: accedi alle voci di Teknopedia che trattano di Matematica