Reproduction of Results from the Literature and Pedagogical Contributions
The Vertex Coloring Problem according to Brooks' Theorem
DOI:
https://doi.org/10.20873/uft.2675-3588.2026.v7n2.p61-70Keywords:
Graph Theory, Graph Coloring, Brooks' Theorem, Chromatic NumberAbstract
This study reproduces a complete proof of Brooks' Theorem, one of the fundamental results in Graph Coloring. The aim is not only to consolidate theoretical knowledge but also to produce didactic support material for the academic community, translating the complexity of the proof through illustrative examples, figures, and detailed explanations. The theorem establishes an upper bound for the chromatic number χ(G) of any connected graph with its maximum degree Δ(G), such that the analyzed graph is neither an odd cycle nor a complete graph. The methodology employed is proof by contradiction, assuming a minimal counterexample, integrated with two crucial techniques, along with illustrations to facilitate teaching. The proof begins with Lovász's Structural Lemma, which is applied to resolve the case of Δ-regular and non-complete graphs. Furthermore, the use of Kempe Chains justification allows us to demonstrate that the structural failure of the coloring is only possible in exceptional cases where the graph is complete or an odd cycle. The result is the confirmation that χ(G) ≤ Δ(G) for every connected graph, except for the forbidden cases.
Downloads
Published
How to Cite
License
Copyright (c) 2026 Matheus Silva Pontes, Lucas Monteiro de Carvalho, Daniel Martins da Silva, Tanilson Dias dos Santos
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Authors who publish in this journal agree to the following terms:
- Authors retain copyright and grant the journal the right of first publication, with work simultaneously licensed under the Creative Commons Attribution License (CC BY-NC 4.0), allowing work sharing with acknowledgment of the work's authorship and initial publication in this journal. ;
- Authors are authorized to enter additional contracts separately for the non-exclusive distribution of the version of the work published in this journal (eg, publishing in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal;
- Authors are allowed and encouraged to post and distribute their work online (eg, in institutional repositories or on their personal page) at any point after the editorial process;
- In addition, the AUTHOR is informed and agrees with the journal that, therefore, his paper may be incorporated by the AJCEAM into existing or existing scientific information systems and databases (indexers and databases). in the future (indexers and future databases), under the conditions defined by the latter at all times, which will involve at least the possibility that the holders of these databases may perform the following actions on the paper:
- Reproduce, transmit and distribute the paper in whole or in part in any form or means of existing or future electronic transmission, including electronic transmission for research, viewing and printing purposes;
- Reproduce and distribute all or part of the article in print;
- Translate certain parts of the paper;
- Extract figures, tables, illustrations, and other graphic objects and capture metadata, captions, and related article for research, visualization, and printing purposes;
- Transmission, distribution, and reproduction by agents or authorized by the owners of database distributors;
- The preparation of bibliographic citations, summaries and indexes and related capture references from selected parts of the paper;
- Scan and/or store electronic article images and text.
