Cultivating Cluster Trees

For any (randomized) distributed algorithm, there are input graphs with $n$ nodes and maximum degree $\Delta$ on which $\Omega(\min\{\sqrt{\log n/\log \log n},\log \Delta/\log \log \Delta\})$ (expected) communication rounds are required to obtain polylogarithmic approximations to a minimum vertex cover, minimum dominating set, or maximum matching.
Via reduction, the hardness extends to symmetry breaking tasks like finding maximal independent sets or maximal matchings.

Today, despite its significance, there is still no proof of this result that is easily digestible.
We provide such a proof, exploiting the characteristics of the construction underlying the lower bound: a family of hard graphs called Cluster Trees.