Discharging method (discrete mathematics)
Encyclopedia
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. Many discharging arguments use one of a few standard initial charge functions (these are listed below). Successful application of the discharging method requires creative design of discharging rules.
Theorem: If a planar graph
has minimum degree 5, then it either has an edge
with endpoints both of degree 5 or one with endpoints of degrees 5 and 6.
Proof:
We use
, 
, and 
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 (for the following reason). 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.
We give the charge
to each vertex 
and the charge 
to each face 
, where 
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 Euler's Formula, it's easy to see that the sum of all the charges is 12:
We use only a single discharging rule:
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
.
The initial charge of each vertex v is
.
So, the final charge of each vertex is at most
. 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.
If a vertex
has degree 5 or 6 and has positive final charge, then v received charge from an adjacent degree 5 vertex 
, so edge 
is light. If a vertex 
has degree 7 and has positive final charge, then 
received charge from at least 6 adjacent degree 5 vertices. Since the graph is a triangulation, the vertices adjacent to 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 
must be adjacent to each other on this cycle. This yields the light edge.
Lemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
in structural graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
. Discharging is most well known for its central role in the proof of the Four Color Theorem
Four color theorem
In mathematics, the four color theorem, or the four color map theorem states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color...
. 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
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
.
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. Many discharging arguments use one of a few standard initial charge functions (these are listed below). Successful application of the discharging method requires creative design of discharging rules.
An easy example
In 1904, Wernicke introduced the discharging method to prove the following theorem, which was part of an attempt to prove the four color theorem.Theorem: If a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
has minimum degree 5, then it either has an edge
with endpoints both of degree 5 or one with endpoints of degrees 5 and 6.
Proof:
We use
, , and 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 (for the following reason). 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.
We give the charge
to each vertex and the charge to each face , where 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 Euler's Formula, it's easy to see that the sum of all the charges is 12:We use only a single discharging rule:
- Each degree 5 vertex gives a charge of 1/5 to each neighbor.
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
.The initial charge of each vertex v is
.So, the final charge of each vertex is at most
. 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.If a vertex
has degree 5 or 6 and has positive final charge, then v received charge from an adjacent degree 5 vertex , so edge is light. If a vertex has degree 7 and has positive final charge, then received charge from at least 6 adjacent degree 5 vertices. Since the graph is a triangulation, the vertices adjacent to 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 must be adjacent to each other on this cycle. This yields the light edge.