En théorie des graphes, un invariant de graphe est une quantité qui n'est pas modifiée par isomorphisme de graphes. Un invariant de graphe ne dépend donc que de la structure abstraite et pas des particularités de la représentation comme l'étiquetage ou le tracé.

De nombreux invariants sont conservés par certains préordres ou ordres partiels naturels sur les graphes^[1] :

• Une propriété est monotone si elle est héritée par les sous-graphes. Le caractère biparti, sans triangle, ou planaire sont des exemples de propriétés monotones.
• Une propriété est héréditaire si elle est héritée par les sous-graphes induits. Toute propriété monotone est donc héréditaire. Le caractère parfait est un exemple de propriété héréditaire non monotone.
• Une propriété est close par mineur si elle est héritée par les mineurs. Le caractère planaire est un exemple de propriété close par mineur.

• Graphe connexe
• Graphe biparti
• Graphe planaire
• Graphe sans triangle
• Graphe parfait
• Graphe eulérien
• Graphe hamiltonien

• Ordre et taille (nombre de sommets et d'arêtes respectivement)
• Nombre de composantes connexes
• Diamètre
• Rayon
• Maille
• Sommet-connexité
• Arête-connexité
• Nombre chromatique
• Nombre achromatique
• Indice chromatique
• Taille du stable maximum
• Nombre de clique
• Arboricité
• Dégénérescence
• Dimension
• Nombre de Strahler
• Nombre domatique

• Coefficient de clustering
• Centralité d'intermédiarité
• Taux d'expansion
• Densité d'un graphe
• Invariant de Parry-Sullivan

• Polynôme caractéristique de la matrice d'adjacence
• Polynôme chromatique
• Polynôme de Tutte

• Portail de l'informatique théorique
• Portail des mathématiques