La somme des degrés d’un graphe non orienté est égal à deux fois le nombre d’arêtes du graphe.

Corollaire : Un graphe a un nombre pair de sommets de degré impair.

Soit A la matrice associée à un graphe.  Le terme  de la matrice  donne le nombre de chaînes de longueur n reliant i à j.

Le nombre chromatique d’un graphe est inférieur ou égal à ,  étant le plus haut degré des sommets.

Le nombre chromatique d’un graphe complet d’ordre n vaut n.

§         Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair vaut 0 ou 2.

§         Un graphe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.

Si M est la matrice de transition d’un graphe probabiliste à n sommets, si  est la matrice ligne décrivant l’état initial et  l’état probabiliste à l’étape n, on a :

Pour tout graphe probabiliste d’ordre 2 dont la matrice de transition ne comporte pas de 0, l’état  à l’étape n converge vers un état P indépendant de l’état initial  et de plus P vérifie

§         Étape 1 : Ordonner les sommets du plus haut degré vers le degré le plus faible.

§         Étape 2 : En parcourant la liste dans l’ordre, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur.

§         Étape 3 : S’il reste des sommets non colorés, retourner à l’étape 2, sinon, la coloration est terminée.

§         Étape 0 : On affecte le poids 0 à D et on attribue provisoirement aux sommets adjacents à D les poids des arêtes qui les relient à D le poids . On désigne par Pl’ensemble des sommets dont le poids est fixé.

§         Étape 1 : Tant que P  ne contient pas l’ensemble des sommets ou que le sommet A n’est pas affecté du plus petit des poids provisoires, exécuter les actions suivantes.

ØParmi tous les sommets provisoirement pondérés, fixer définitivement le poids d’un de ceux qui ont un poids minimum. Soit T ce sommet.

ØAjouter ce sommet à P.

ØPour tout sommet T’ n’appartenant pas à P et adjacent à T,  calculer la somme s du poids de Tet du poids de l’arête reliant T à T’ ; si s est inférieur au poids provisoire de T’, affecter s à T’ comme nouveau poids provisoire et le marquer s(T) pour marquer la provenance de cette affectation.