Exécution de notre outil de synthèse sur un nouvel article

Résumé : This chapter gives an overview of several classical topics in the study of graph theory, including perfect matchings, Hamilton cycles, Eulerian trails, proper vertex- and edge-colourings, and connectivity. We begin by proving Hall’s theorem on perfect matchings, Kőnig’s theorem on vertex-covers, and Dirac’s theorem on the minimum degree threshold for a graph to contain a Hamilton cycle. The middle third of the chapter focuses on proper colourings; in particular, we give elegant proofs of Brooks’ theorem on vertex-colourings and Vizing’s theorem on edge-colourings. To finish the chapter, we prove the famous Max-Flow Min-Cut theorem of Ford and Fulkerson, and the fundamental theorems of Menger and Mader on k -connectivity