Metraipolis › archive › dc_6a32a70ac8a8

Discharging method (discrete mathematics) — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T11:32:52.811Z
SHA-256 of the archived text
25d7aa0aee58dd449e093e1fc2bd0b31d4656f2fe9155f96ef133e61877c99a5
Stable URL of this page
https://metraipolis.com/documento/dc_6a32a70ac8a8

How to cite

Discharging method (discrete mathematics) — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_6a32a70ac8a8 (Metraipolis archive dc_6a32a70ac8a8, sha256 25d7aa0aee58dd449e093e1fc2bd0b31d4656f2fe9155f96ef133e61877c99a5)
BibTeX
@misc{dc6a32a70ac8a8,
  title = {Discharging method (discrete mathematics) — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_6a32a70ac8a8; sha256 25d7aa0aee58dd449e093e1fc2bd0b31d4656f2fe9155f96ef133e61877c99a5},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics). Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The discharging method is a technique used to prove lemmas in structural graph theory. Discharging is most well known for its central role in the proof of the four color theorem. The discharging method is used to prove that every graph in a certain class contains some subgraph from a specified list. The presence of the desired subgraph is then often used to prove a coloring result. Most commonly, discharging is applied to planar graphs. Initially, a charge is assigned to each face and each vertex of the graph. The charges are assigned so that they sum to a small positive number. During the Discharging Phase the charge at each face or vertex may be redistributed to nearby faces and vertices, as required by a set of discharging rules. However, each discharging rule maintains the sum of the charges. The rules are designed so that after the discharging phase each face or vertex with positive charge lies in one of the desired subgraphs. Since the sum of the charges is positive, some face or vertex must have a positive charge. A well-known example of the discharging method is in proofs of the four color theorem for planar graphs, where it was used to obtain certain "unavoidable configurations" whose existence prevents all planar graphs from being minimal counterexamples to the theorem. A very complicated and computer-based case analysis for this method, from the original proof by Kenneth Appel and Wolfgang Haken, was later simplified by Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas., but the simplified proof remains complex, with "many configurations and rules".

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»).
Fonte: Wikipedia in inglese, voce «Discharging method (discrete mathematics)» — https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)
Wikidata Q5281445: «technique used to Prove Lemmas in Structural Graph Theory» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5281445
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1322434919, consultata il 2026-10-06T09:55:39.872Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 7903ad172225d2d3ba09863e5cdeadcf09783bfe3b5aff6b2a3a1f7b18a875b0