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
Examples of simple charging schemes
graph theory;cg.comp geom;examples