Grafo semplice

Si dice grafo semplice un grafo non diretto^[1] che non comprende cappi e archi multipli.

I grafi semplici sono logicamente equivalenti alle relazioni simmetriche antiriflessive. Quindi la matrice delle adiacenze di un grafo semplice è una matrice binaria simmetrica avente nulle tutte le entrate della diagonale principale. Viceversa, ogni matrice di questo tipo rappresenta un grafo semplice.

Di solito per grafo semplice si intende un grafo finito, cioè un grafo che presenta un insieme finito di nodi. Talora possono essere utili anche grafi semplici infiniti.

Gran parte delle teoria dei grafi non orientati riguarda i grafi semplici: infatti per molte proprietà dei grafi la presenza di cappi (o di archi multipli) non ha alcuna influenza. Questo accade ad esempio per proprietà come raggiungibilità, esistenza di cammini hamiltoniani, colorabilità, planarità e connettività dei diversi tipi. All'opposto, i problemi riguardanti i cammini euleriani riguardano naturalmente grafi che presentani spigoli multipli (o digrafi che presentano archi multipli).

Coerentemente, quasi tutte le applicazioni dei grafi non orientati ad altre questioni matematiche si servono di grafi semplici. Ad esempio, sono grafi semplici i grafi associati ai poliedri. Per la classificazione delle algebre di Lie semisemplici servono invece grafi con spigoli multipli, come i diagrammi di Coxeter-Dynkin.