Duality between chip-firing games and graph divisor theory

There is a duality between the notion of graph divisor theory and chip-firing, which was discovered by Baker and Norine .

Let $$G$$ be a graph and let $$K^+ = K^+_G$$ be the chip-distribution with $$K^+(v)=d(v) - 1$$ for each vertex $$v$$ .

For a divisor $$D\in Div(G)$$ with $$D(v)\leq d(v)-1$$ for each $$v\in V(G)$$ , we call $$K^+ - D\geq 0$$ the dual pair of $$D$$ . Note that each chip-distribution is a dual pair of some divisor.

The following proposition of Baker and Norine is the key ingredient of the duality:

Theorem. For a divisor $$D\in Div(G)$$ with $$D(v)\leq d(v)-1$$ for each $$v\in V(G)$$ , there exists an effective divisor equivalent to $$D$$ if and only if $$K^+ - D$$ is a terminating chip-distribution.

The following is a straightforward consequence of the above theorem.

Theorem. Let $$D \in Div(G)$$ be a divisor with $$f(v)\leq d(v)-1$$ for each $$v\in V(G)$$ , and let $$x \in Chip(G)$$ be its dual pair. Then $$rank(f) = dist(x) - 1$$ .