Les dix chapitres de ce cours recouvrent l’ensemble de la théorie des graphes, des notions de base jusqu’aux développements les plus récents, y compris des conjectures encore ouvertes ; ils ont pour titres :
– Concepts fondamentaux
– Quelques graphes remarquables
– (Di)graphes et structures de données
– Connexité et flots dans les réseaux
– Graphes planaires
– Théorie algébrique
– Coloration
– Couplage et factorisation
– Automorphismes
– Théorie spectrale
– Autres perspectives
– Ils sont complétés par une bibliographie, un index et une liste de symboles, très complets.

La plupart des notions sont introduites par le problème « concret » qui est à leur source (ponts de Königsberg, problème des mariages, coloration de cartes…) ; mention est faite de leurs domaines d’application (télécommunications, recherche opérationnelle, informatique parallèle, algorithmique, physique statistique, …) mais la théorie est ensuite développée abstraitement, et classiquement : définitions, propriétés et théorèmes, démonstrations On trouve, chaque fois que c’est utile, des rappels relatifs aux autres domaines mathématiques qui interfèrent avec les graphes : topologie, algèbre matricielle, théorie des groupes… L’aspect algorithmique est omniprésent.
Des exercices sont inclus au fil du texte ; il s’agit d’applications directes du cours, ou de démonstrations simples de propriétés.