In rigidity theory and sparse graph algorithms, a pebble game is an algorithm that uses pebbles as movable markers to certify graph sparsity. The 
-pebble games characterize and recognize graphs for which
every subset of 
vertices spans at most 
edges. The case in which equality holds for the whole graph is called tight. In particular,
the 
-tight case recognizes Laman
graphs, which are the minimally rigid graphs in the plane by Laman's
theorem (Lee and Streinu 2008).
This use of the term is distinct from graph pebbling, in which pebbling moves consume pebbles in transit and lead to invariants such as the pebbling number.
