Discharging method (discrete mathematics)

<h2 id="an-example">An example</h2>
In 1904, Wernicke introduced the discharging method to prove the following theorem, which was part of an attempt to prove the four color theorem.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
Theorem: If a <a href="/facts/Planar_graph/plREagr9">planar graph</a> has minimum <a href="/facts/Degree_(graph_theory)/LnFFpI8v">degree</a> 5, then it either has an edge
with endpoints both of degree 5 or one with endpoints of degrees 5 and 6.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Proof:
We use 
 
 
 
 V
 
 
 {\displaystyle V}
 
, 
 
 
 
 F
 
 
 {\displaystyle F}
 
, and 
 
 
 
 E
 
 
 {\displaystyle E}
 
 to denote the sets of vertices, faces, and edges, respectively.
We call an edge light if its endpoints are both of degree 5 or are of degrees 5 and 6.
Embed the graph in the plane. To prove the theorem, it is sufficient to only consider planar triangulations (because, if it holds on a triangulation, when removing nodes to return to the original graph, neither node on either side of the desired edge can be removed without reducing the minimum degree of the graph below 5). We arbitrarily add edges to the graph until it is a triangulation. 
Since the original graph had minimum degree 5, each endpoint of a new edge has degree at least 6. 
So, none of the new edges are light.
Thus, if the triangulation contains a light edge, then that edge must have been in the original graph.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
We give the charge 
 
 
 
 6
 −
 d
 (
 v
 )
 
 
 {\displaystyle 6-d(v)}
 
 to each vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 and the charge 
 
 
 
 6
 −
 2
 d
 (
 f
 )
 
 
 {\displaystyle 6-2d(f)}
 
 to each face 
 
 
 
 f
 
 
 {\displaystyle f}
 
, where 
 
 
 
 d
 (
 x
 )
 
 
 {\displaystyle d(x)}
 
 denotes the degree of a vertex and the length of a face. (Since the graph is a triangulation, the charge on each face is 0.) Recall that the sum of all the degrees in the graph is equal to twice the number of edges; similarly, the sum of all the face lengths equals twice the number of edges. Using <a href="/facts/Planar_graph/plREagr9">Euler's Formula</a>, it's easy to see that the sum of all the charges is 12:<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

 
 
 
 
 
 
 
 
 ∑
 
 f
 ∈
 F
 
 
 6
 −
 2
 d
 (
 f
 )
 +
 
 ∑
 
 v
 ∈
 V
 
 
 6
 −
 d
 (
 v
 )
 =
 
 
 
 
 
 6
 
 |
 
 F
 
 |
 
 −
 2
 (
 2
 
 |
 
 E
 
 |
 
 )
 +
 6
 
 |
 
 V
 
 |
 
 −
 2
 
 |
 
 E
 
 |
 
 =
 
 
 
 
 
 6
 (
 
 |
 
 F
 
 |
 
 −
 
 |
 
 E
 
 |
 
 +
 
 |
 
 V
 
 |
 
 )
 =
 
 
 
 12.
 
 
 
 
 
 
 {\displaystyle {\begin{aligned}\sum _{f\in F}6-2d(f)+\sum _{v\in V}6-d(v)=&\\6|F|-2(2|E|)+6|V|-2|E|=&\\6(|F|-|E|+|V|)=&&12.\end{aligned}}}

We use only a single discharging rule: Each degree 5 vertex gives a charge of 1/5 to each neighbor.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>
We consider which vertices could have positive final charge.
The only vertices with positive initial charge are vertices of degree 5. 
Each degree 5 vertex gives a charge of 1/5 to each neighbor. 
So, each vertex is given a total charge of at most 
 
 
 
 d
 (
 v
 )
 
 /
 
 5
 
 
 {\displaystyle d(v)/5}
 
. 
The initial charge of each vertex v is 
 
 
 
 6
 −
 d
 (
 v
 )
 
 
 {\displaystyle 6-d(v)}
 
. 
So, the final charge of each vertex is at most 
 
 
 
 6
 −
 4
 d
 (
 v
 )
 
 /
 
 5
 
 
 {\displaystyle 6-4d(v)/5}
 
. Hence, a vertex can only have positive final charge if it has degree at most 7. Now we show that each vertex with positive final charge is adjacent to an endpoint of a light edge.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a>
If a vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 has degree 5 or 6 and has positive final charge, then 
 
 
 
 v
 
 
 {\displaystyle v}
 
 received charge from an adjacent degree 5 vertex 
 
 
 
 u
 
 
 {\displaystyle u}
 
, so edge 
 
 
 
 u
 v
 
 
 {\displaystyle uv}
 
 is light. If a vertex 
 
 
 
 v
 
 
 {\displaystyle v}
 
 has degree 7 and has positive final charge, then 
 
 
 
 v
 
 
 {\displaystyle v}
 
 received charge from at least 6 adjacent degree 5 vertices. Since the graph is a triangulation, the vertices adjacent to 
 
 
 
 v
 
 
 {\displaystyle v}
 
 must form a cycle, and since it has only degree 7, the degree 5 neighbors cannot be all separated by vertices of higher degree; at least two of the degree 5 neighbors of 
 
 
 
 v
 
 
 {\displaystyle v}
 
 must be adjacent to each other on this cycle. This yields the light edge.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Cranston, Daniel W.; West, Douglas B. (1 April 2017), "An introduction to the discharging method via graph coloring", Discrete Mathematics, 340 (4): 766–793, arXiv:1306.4434, doi:10.1016/j.disc.2016.11.022, ISSN 0012-365X, retrieved 25 February 2023 <a href="https://www.sciencedirect.com/science/article/pii/S0012365X1630379X" target="_blank">https://www.sciencedirect.com/science/article/pii/S0012365X1630379X</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Cranston, Daniel W.; West, Douglas B. (1 April 2017), "An introduction to the discharging method via graph coloring", Discrete Mathematics, 340 (4): 766–793, arXiv:1306.4434, doi:10.1016/j.disc.2016.11.022, ISSN 0012-365X, retrieved 25 February 2023 <a href="https://www.sciencedirect.com/science/article/pii/S0012365X1630379X" target="_blank">https://www.sciencedirect.com/science/article/pii/S0012365X1630379X</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hliněný, Petr (2000), Discharging technique in practice. (Lecture text for Spring School on Combinatorics). <a href="http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps" target="_blank">http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Hliněný, Petr (2000), Discharging technique in practice. (Lecture text for Spring School on Combinatorics). <a href="http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps" target="_blank">http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Appel, Kenneth; Haken, Wolfgang (1977), "Every planar map is four colorable. I. Discharging", Illinois Journal of Mathematics, 21: 429–490, doi:10.1215/ijm/1256049011 <a href="/wiki/Kenneth_Appel" target="_blank">/wiki/Kenneth_Appel</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Appel, Kenneth; Haken, Wolfgang (1977), "Every planar map is four colorable. II. Reducibility", Illinois Journal of Mathematics, 21: 491–567, doi:10.1215/ijm/1256049012 <a href="/wiki/Kenneth_Appel" target="_blank">/wiki/Kenneth_Appel</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin (1997), "The four-color theorem", Journal of Combinatorial Theory, Series B, 70: 2–44, doi:10.1006/jctb.1997.1750 <a href="/wiki/Neil_Robertson_(mathematician)" target="_blank">/wiki/Neil_Robertson_(mathematician)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Hliněný, Petr (2000), Discharging technique in practice. (Lecture text for Spring School on Combinatorics). <a href="http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps" target="_blank">http://kam.mff.cuni.cz/~kamserie/serie/clanky/2000/s475.ps</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz", Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 <a href="https://zenodo.org/record/1428228" target="_blank">https://zenodo.org/record/1428228</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
</ol>

Discharging method (discrete mathematics) open-in-new

Discharging method (discrete mathematics)