I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope to find something more graph-theoretic.
My geometric example is about upper bounding the complexity of an envelope of squares, (that is, how many vertices can appear in the union of $n$ squares, counting only vertices that are on the border / not contained in the interior of another square). We allow the squares to have different sizes. A vertex on the envelope is either a vertex of a square or an intersection point of two squares, and thus, we immediately obtain a quadratic upper bound. A very simple charging scheme yields a linear bound.
We wish to charge every vertex of the envelope to a vertex of a square, such that every square vertex will be charged at most twice. This will immediately imply that there are at most $8n$ vertices on the envelope. A vertex of the envelope that is also a vertex of a square will charge itself. Let $p$ be a vertex of the envelope that is formed by the intersection of the squares $A,B$ such that $A$ is larger or equal to $B$. We travel from $p$ along the edge of $B$ in the direction that enters the interior of $A$, and charge the vertex of $B$ that is at the end of this edge. By drawing this, it is easy to verify that every vertex is indeed charged at most twice.
I hope that you will agree that this charging scheme can be explained in a talk in 1-2 minutes. Are there any such simple graph-theoretic examples?
Many thanks, Adam