La
théorie des graphes est une théorie
informatique et
mathématique. Les
algorithmes élaborés pour résoudre des problèmes concernant les
objets de cette théorie ont de nombreuses applications dans tous les domaines liés à la notion de réseau (
réseau social,
réseau informatique,
télécommunications, etc.) et dans bien d'autres domaines (par exemple
génétique) tant le concept de graphe, à peu près équivalent à celui de
relation binaire (à ne pas confondre donc avec
graphe d'une fonction), est général. De grands théorèmes difficiles, comme le
théorème des quatre couleurs, le
théorème des graphes parfaits, ou encore le
théorème de Robertson-Seymour, ont contribué à asseoir cette matière auprès des mathématiciens, et les questions qu'elle laisse ouvertes, comme la
conjecture d'Hadwiger, en font une branche vivace des
mathématiques discrètes.
