Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs

Statement

The discharging method is a proof technique in structural/extremal graph theory for showing that *every* graph in some class $\mathcal G$ (typically: planar graphs, or graphs with a bounded density parameter such as maximum average degree $\mathrm{mad}(G)<b$) must contain at least one member of a specified finite list of small local structures — a vertex or face of low degree with a constrained neighborhood, a short cycle, a "reducible configuration." It converts a global combinatorial/topological invariant (Euler's formula for planar graphs, or an average-degree bound for sparse graphs) into a local pigeonhole contradiction. Per en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics): "the discharging method is a technique used to prove lemmas in structural graph theory" by showing "every graph in a certain class contains some subgraph from a specified list," which then feeds a coloring (or other extremal) argument.

The general recipe (three moving parts, per Wikipedia + Cranston–West arXiv:1306.4434):

1. Charge assignment. Assign an *initial charge* $\mathrm{ch}(x)$ to every vertex $x$ (planar case: often to faces too), chosen so the total charge is a known constant forced by a global identity: - *Classical planar/4CT form* (triangulation, en.wikipedia.org/wiki/Four_color_theorem): $\mathrm{ch}(v) = 6-\deg(v)$ for each vertex $v$. Since a planar triangulation satisfies $2e=3f$ and Euler's formula $v-e+f=2$, one derives $\sum_v (6-\deg(v)) = 12$ — a fixed positive constant independent of the graph's size. - *Modern sparse/"mad" form* (Cranston–West, Definition 1.1, arXiv:1306.4434): $\mathrm{ch}(v)=\deg(v)$ for every vertex; the hypothesis $\mathrm{mad}(G) < b$ (maximum average degree over all subgraphs) forces $\sum_v \mathrm{ch}(v) = \sum_v \deg(v) < b\,|V(G)|$, i.e. the average final charge must stay below $b$. 2. Discharging rules. A finite list of local rules that move fixed amounts of charge between nearby vertices/faces (e.g. "a 2-vertex takes $\tfrac12$ from each neighbor," Cranston–West Lemma 1.3). Every rule conserves the sum, so total charge is invariant under discharging. 3. Contradiction. Show that *if* no forbidden/reducible local configuration occurs, the rules force every vertex/face to end with charge $\le 0$ (planar form) or $\ge b$ (mad form) — contradicting the known total (positive $12$, or average $<b$). Hence some forbidden configuration must exist in any graph satisfying the hypothesis; equivalently, no minimal counterexample to the target theorem can avoid it.

Companion machinery for coloring proofs (4CT-style)

the contradiction step is usually run against a minimal counterexample $G$ (fewest vertices, or fewest edges among those) to the coloring theorem being proved. One then needs (a) an unavoidable set: a finite list of local configurations such that every minimal counterexample must contain at least one of them (proved by discharging, as above), and (b) reducibility: a proof that each configuration in the unavoidable set in fact *cannot* occur in a minimal counterexample (usually by exhibiting a smaller graph, recoloring it by the induction hypothesis, and showing the coloring extends back — often checked exhaustively/by computer). Unavoidability + reducibility for every member of the list together contradict the existence of any minimal counterexample, proving the theorem for all graphs in $\mathcal G$. (Definitions per WebSearch cross-checked summary of the discharging/4CT literature, consistent with the Wikipedia and Four-color-theorem pages fetched above.)

Facts

- Origin: Wernicke (1904) used an early discharging-style argument for planar graphs of minimum degree 5, in pursuit of the four color theorem (en.wikipedia.org/wiki/Discharging_method_(discrete_mathematics)). Heesch (1969, later 1970s) coined/systematized the method and conjectured it could be pushed to a full proof of the four color theorem, but lacked the computational power to complete the case analysis. - Four Color Theorem (Appel & Haken, 1976/1977): the first complete proof, combining discharging with massive computer-assisted case-checking. It used an unavoidable set of (reported, per Wikipedia) roughly 1,834 configurations reduced to about 1,482 reducible configurations, requiring over 1,000 hours of computer verification. - Robertson, Sanders, Seymour & Thomas (1997) gave a simplified proof with a smaller unavoidable set of 633 reducible configurations and a quadratic-time coloring algorithm, still computer-assisted but far more tractable (en.wikipedia.org/wiki/Four_color_theorem). - Modern generalization beyond planarity — "maximum average degree" (mad) discharging. Cranston & West, "An Introduction to the Discharging Method via Graph Coloring" (arXiv:1306.4434, published *Discrete Mathematics* 340(4):766–793, 2017): the same charge/rule/contradiction skeleton is used with $\mathrm{ch}(v)=\deg(v)$ and hypothesis $\mathrm{mad}(G)<b$ instead of Euler's formula — this decouples the method from planarity entirely and is the workhorse for modern sparse-graph coloring results (list coloring, acyclic/star coloring, circular coloring, edge coloring, linear arboricity). Worked examples given: Theorem 1.6 (edge coloring: $\mathrm{mad}(G)<3,\ \Delta(G)\ge6 \Rightarrow \chi'(G)=\Delta(G)$); Theorem 2.3 (acyclic 6-choosability under $\mathrm{mad}(G)<3$); Theorem 2.8/2.11 (fractional/circular coloring under girth + mad hypotheses). - Reverse-engineering the threshold ("start with the proof and let it produce the statement"), Cranston–West Remarks 2.1/2.6: the sharp constant $b$ in a mad-hypothesis theorem is typically *derived*, not guessed — write the discharging rules symbolically with a free parameter $\rho$ (how much charge a low-degree vertex pulls from each higher-degree neighbor), solve the tightness equation (e.g. "$2+2\rho=(j+1)(1-\rho)$" giving $\rho=(j-1)/(j+3)$ and $b=2+2\rho=4(j+1)/(j+3)$) so every inequality is exactly tight, and read off $b$. Sharpness/tight examples are then built with all vertices of degree 2 or 3. - Discharging for cycle-existence, not just coloring — directly relevant to this wiki's Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle cluster: Heckman & Krakovski (2013, *Electron. J. Combin.* 20(2) #P7, see Erdős–Gyárfás conjecture confirmed for 3-connected cubic planar graphs (Heckman–Krakovski 2013)) prove the Erdős–Gyárfás conjecture (every min-degree-$\ge3$ graph has a $2^m$-cycle) for 3-connected cubic planar graphs, by a discharging argument: charge $\mathrm{ch}(v)=4-\deg(v)$ (so every cubic vertex starts at $+1$) and $\mathrm{ch}(f)=4-|f|$ per face, giving total charge $8>0$ by Euler's formula; 15 explicit discharging rules must drive every vertex/face to charge $\le0$, and the paper's genuine methodological novelty is computing the hardest per-face charge bounds by solving small integer linear programs rather than hand-checking cases — i.e. discharging with a computer-optimization oracle standing in for manual reducible-configuration enumeration. - Discharging as a general "local rule → global counting contradiction" template recurs even without an explicit charge function: Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic (Avery Carr, arXiv:2605.22844, 2026) uses the same two-step shape — minimality forces a local structural constraint, then a global edge-cut/double-counting inequality forces a density bound — to show any minimal Erdős–Gyárfás counterexample is $\ge \tfrac47$ cubic, without running a full discharging scheme (this wiki's own cross-reference flags it as "cheap enough... a single edge-cut inequality suffices"). - Girth-restricted planar coloring is the other classical discharging battleground (e.g. Grötzsch-type planar 3-/4-coloring results under girth $\ge g$ hypotheses, and the fractional/circular-coloring theorems in Cranston–West §2 above) — a large modern literature (see e.g. arXiv:1505.03197, arXiv:1611.03454, arXiv:2205.07968, arXiv:2509.06808 for representative recent discharging papers on planar list/injective/square coloring, found via WebSearch, not independently read in full this session). - Recent progress on shrinking the 4CT case analysis: a 2026 preprint, "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring" (arXiv:2603.24880, title/abstract found via WebSearch only, not independently fetched), reportedly reduces the unavoidable set further and improves the coloring algorithm's runtime — flagged here as an unverified pointer for follow-up, not confirmed content.

Technique

WHEN it applies: the target class of graphs must carry a global density/topological invariant that can be turned into an exact or bounded total over vertices/faces — either (a) planarity, via Euler's formula ($v-e+f=2$), typically after reducing to a triangulation or otherwise controlling face lengths, or (b) a bounded maximum average degree $\mathrm{mad}(G)<b$ (which subsumes girth-restricted planar graphs, since planar graphs of girth $\ge g$ have $\mathrm{mad}(G) < \frac{2g}{g-2}$). The goal must be expressible as "graphs in this class always contain [a specific small local structure]" — a low-degree vertex with a constrained neighborhood, a short cycle, a face of bounded size — which then typically feeds an inductive coloring proof (remove/contract the forced structure, color the rest by induction, extend back) or, as in the Erdős–Gyárfás case, directly witnesses the target existential structure (a $2^m$-cycle).

HOW to run it (concrete steps, reusable): 1. Set up the minimal-counterexample (or direct universal) framing. For coloring theorems: assume $G$ is a smallest (by vertices, then edges) graph in the class that is *not* colorable as claimed; minimality gives you the freedom to delete/contract any local piece, recolor by induction, and derive constraints from the fact that the coloring must fail to extend. For direct structural theorems (no coloring, e.g. cycle existence): the "minimal counterexample" role may instead just be the graph itself, with discharging proving a positive-charge witness must exist somewhere. 2. Choose the charge function to match the invariant. Planar/Euler's-formula setting: $\mathrm{ch}(v)=6-\deg(v)$ (or a variant like $4-\deg(v)$ scaled to the target face lengths, as in Heckman–Krakovski) plus a matching face charge, chosen so $\sum \mathrm{ch} = $ a fixed constant via Euler's formula. Mad setting: $\mathrm{ch}(v)=\deg(v)$, with the hypothesis $\mathrm{mad}(G)<b$ bounding $\sum\mathrm{ch}(v)$ from above. 3. Design discharging rules that push charge from "rich" vertices/faces (high degree / large face) toward "poor" ones (low degree / small face) that need to end up positive (or, in the mad framing, push charge away from low-degree vertices that would otherwise stay below $b$). Rules are local (depend only on a bounded neighborhood) and exactly conserve the sum. 4. Prove the discharging rules are sufficient: case-split on all possible local configurations around a vertex/face and check that after applying the rules, the final charge is always $\le0$ (planar) or $\ge b$ (mad) *unless* one of a finite list of forbidden/target configurations is present nearby. This is the technically heaviest step and is where computer-assisted case analysis (Appel–Haken, RSST) or an ILP oracle (Heckman–Krakovski) gets used when the case count is too large for hand-checking. 5. Chain the two bounds into a contradiction (or existence proof): total charge is provably a fixed positive constant (or bounded average) by the global invariant (step 2), yet the local rules (step 4) force it to be $\le0$ everywhere in the absence of the target structure — contradiction, so the target structure must occur. For coloring proofs, feed this into the unavoidable-set + reducibility argument (§Statement) to rule out the minimal counterexample entirely.

WHY it works (the mechanism, for recombination): discharging exploits the fact that a *global* combinatorial identity (Euler's formula's linear relation among $v,e,f$, or a degree-sum/average-degree bound) can be rewritten as "$\sum_x \mathrm{ch}(x) = C$" for *any* choice of charge function summing to the same linear combination of degrees/face-lengths — this gives total freedom to *redesign* the charge function and rules to target whatever local structure the theorem needs, while the total stays pinned by topology/density alone. The redistribution step is where all the "proof work" lives, but it is a finite, local, case-checkable problem (bounded-radius neighborhoods only), which is exactly what makes it amenable to exhaustive human case analysis, computer case-checking (Appel–Haken/RSST), or — the modern innovation illustrated by Heckman–Krakovski — reduction to an optimization problem (ILP) that a solver certifies exactly. This local⇄global conversion is the same abstract shape as double-counting/entropy-style arguments elsewhere in this wiki (see Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao)) but specialized to *conserved local redistribution* rather than *subadditive decomposition*.

Related

- Erdős–Gyárfás conjecture confirmed for 3-connected cubic planar graphs (Heckman–Krakovski 2013) — worked concrete instance: 15 discharging rules + Euler's-formula total charge $8$, with per-face charge bounds computed via integer programming rather than hand-checked; proves a $2^m$-cycle exists in every 3-connected cubic planar graph. - Erdős #64 — min-degree-3 graphs contain a power-of-2 cycle — the still-open general Erdős–Gyárfás conjecture (min-degree-$\ge3$ $\Rightarrow$ power-of-2 cycle) that the discharging-based partial results above all attack restricted cases of. - Carr — any minimal Erdős–Gyárfás counterexample is predominantly cubic — a lighter-weight sibling technique (minimality + single edge-cut double-counting, no full discharging scheme) attacking the same conjecture's minimal-counterexample structure; explicitly contrasted with full discharging in that page's own notes. - Erdős–Gyárfás conjecture confirmed for P8-free and P10-free graphs — restricted-class ($P_8$-/$P_{10}$-free graphs) confirmations of the same conjecture via minimal-counterexample analysis (structurally related but not confirmed to use explicit charge-counting in this wiki's current sourcing). - Erdős #63 — infinite chromatic number ⇒ cycles of length $2^n$ infinitely often — the *infinite chromatic number* power-of-2-cycle problem, solved by an entirely different technique (sublinear expanders, Liu–Montgomery 2020/2023) — a useful contrast showing discharging is not the only route to power-of-2-cycle-type results. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — a different local⇄global proof-conversion technique (subadditive decomposition rather than conserved redistribution); useful structural comparison for how "local pieces sum/bound a global quantity" arguments recur across this wiki. - concept/reducible-configurations — the classical discharging notion (a local structure provably absent from any minimal counterexample) referenced from the Heckman–Krakovski and Erdős–Gyárfás pages above; not yet an independent page in this wiki.