Discharging method (discrete mathematics)

Last updated August 14, 2023

The discharging method is a technique used to prove lemmas in structural graph theory.^[1] 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.^[1]

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 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 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 $V$ , $F$ , and $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.

We give the charge $6-d(v)$ to each vertex $v$ and the charge $6-2d(f)$ to each face $f$ , where $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 Euler's Formula, it's easy to see that the sum of all the charges is 12:

${\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.

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$ . The initial charge of each vertex v is $6-d(v)$ . So, the final charge of each vertex is at most $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.

If a vertex $v$ has degree 5 or 6 and has positive final charge, then $v$ received charge from an adjacent degree 5 vertex $u$ , so edge $uv$ is light. If a vertex $v$ has degree 7 and has positive final charge, then $v$ 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 $v$ must be adjacent to each other on this cycle. This yields the light edge.

Related Research Articles

In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. The proof has gained wide acceptance since then, although some doubters remain.

<span class="mw-page-title-main">Graph theory</span> Area of discrete mathematics

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

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. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs are NP-complete.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In graph theory, two graphs $and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.$

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Sperner's lemma</span> Theorem on triangulation graph colorings

In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring of a triangulation of an $-dimensional$ simplex contains a cell whose vertices all have different colors.

In the mathematical discipline of graph theory, the line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$ . $L(G)$ is constructed in the following way: for each edge in $G$ , make a vertex in $L(G)$ ; for every two edges in $G$ that have a vertex in common, make an edge between their corresponding vertices in $L(G)$ .

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most $k$ different colors, for a given value of $k$ , or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the countries of the world, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig (1931), describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex $v$ in a graph is a vertex that is connected to $v$ by an edge. The neighbourhood of a vertex $v$ in a graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$ , i.e., the graph composed of the vertices adjacent to $v$ and all edges connecting vertices adjacent to $v$ .

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler (1736) in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of $vertices from an n -vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.$

In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

In graph theory, a mathematical discipline, coloring refers to an assignment of colours or labels to vertices, edges and faces of a graph. Defective coloring is a variant of proper vertex coloring. In a proper vertex coloring, the vertices are coloured such that no adjacent vertices have the same colour. In defective coloring, on the other hand, vertices are allowed to have neighbours of the same colour to a certain extent.

References

1 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.

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 .
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 .
Hliněný, Petr (2000), Discharging technique in practice . (Lecture text for Spring School on Combinatorics).
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 .
Wernicke, P. (1904), "Über den kartographischen Vierfarbensatz" (PDF), Math. Ann. (in German), 58 (3): 413–426, doi:10.1007/bf01444968 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[10.1016_j.disc.2016.11.022-1] 1 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.

[1]