Résumé de section

  • In this chapter, we explore important concepts related to cycles and their fundamental role in graph theory. We begin by studying the decomposition of cycles and cocycles, the Arc Colouring Lemma proposed by Minty (1960), and the notions of cycle and cocycle bases. We then introduce the cyclomatic and cocyclomatic numbers, which measure the structure and connectivity of a graph. Next, we address the concept of planarity, where we learn how to determine whether a graph can be drawn on a plane without edge intersections. This section includes Euler’s formula, Kuratowski’s theorem (1930), and the idea of a dual graph. Finally, we study trees, forests, and arborescences, focusing on their definitions, main properties, and the construction of maximum (or spanning) trees, which are key structures in many applications of graph theory.