Discharging method (discrete mathematics)

The discharging method is a powerful technique in discrete mathematics, particularly in graph theory, used to prove structural properties or the existence of certain configurations within graphs or other discrete structures. It is primarily used to prove results about planar graphs, but can be applied to other classes of graphs and even discrete geometric settings.

The fundamental idea is to distribute an "initial charge" to vertices, edges, or faces of the graph (or other structure). This initial charge is typically chosen based on a relevant parameter, such as the degree of a vertex. Then, a series of "discharging rules" are applied, which redistribute the charge according to local conditions. These rules are carefully designed to ensure that the total charge of the system is conserved throughout the discharging process.

The goal is to show that after the discharging process, no element (vertex, edge, or face) has a negative charge. This often implies the existence of a particular structure or the satisfaction of some property. For instance, in the context of planar graphs, showing that no face has a negative charge after discharging can be used to prove bounds on the average degree of vertices or the existence of specific subgraphs.

The discharging rules are typically defined based on the local configuration around a vertex or face. For example, a rule might state that a vertex of high degree sends a certain amount of charge to neighboring vertices of low degree. The choice of appropriate initial charges and discharging rules is crucial for the success of the method. These choices are usually guided by intuition about the structural properties of the graphs being studied and the properties one aims to prove.

A key aspect of the discharging method is the careful accounting of charge transfers. One must rigorously prove that the total charge remains constant throughout the discharging process and that no element ends up with a negative charge. This often involves a detailed case analysis of different possible local configurations.

The discharging method is not an algorithm that outputs a solution directly. Instead, it is a proof technique that demonstrates the existence of some property by showing that a contradiction would arise if the property were not true. If after discharging, a structure has a negative charge, it means that the structural property being proved is present.