An Alternate Proof of Kager's Cut Counting Bound

Given an $n$-vertex graph, the number of cuts whose value is at most $\alpha$ times the global min-cut is at most $O(n^{2\alpha})$. This result is shown in [Karger93], using an elegant random contract algorithm for computing a global min-cut. Later, in subsequent work [Karger00], this bound is improved based on the connection of min-cut and spanning tree packings. In this talk, we will provide alternate proof of the result. The bound given by our proof matches the bound in [Karger00].