Discrete Lunch‎ > ‎

Nov 3: Discharging method

posted Oct 31, 2014, 4:48 AM by Dirk Oliver Theis   [ updated Nov 21, 2014, 4:35 AM ]
Abdullah Makkeh (PhD student) has promised to explain the discharging method from topological graph theory with lots of examples.

The discharging method underlies the proof of the famous Four-Color Theorem: "The vertices of a planar graph can be colored with 4 colors in such a way that no two adjacent vertices receive the same color."

Since its inception, this method has been used to resolve a truckload of problems about planar graphs, and graphs on other surfaces.