Yufei Zhao Graph regularity method and applications to property testing This tutorial gives an introduction to Szemerédi's graph regularity lemma, a powerful tool in graph theory that gives a rough structural description for all graphs, as well as its applications to computer science, in particular to property testing. There are simple sampling algorithms for inferring graph properties or estimating graph parameters from reading a random selection of vertices in a graph, though it is not always obvious how to prove guarantees about these algorithms. The graph regularity lemma provides tools for analyzing these algorithms.