第5步纯粹讨论图与矩阵;现在戈茨曼–利尼亚尔等价关系把它转换回关于布尔函数的陈述。两个水平集 f=0f=0f=0 与 f=1f=1f=1 给出 {0,1}n\{0,1\}^n{0,1}n 中互为补集的诱导子图,而该等价关系针对非平衡情形表述,并不声称某一个水平集总有至少 2n−1+12^{n-1}+12n−1+1 个顶点。
戈茨曼与利尼亚尔(1992年)证明,Γ(H)≥h(n) for every H with ∣V(H)∣≠2n−1\Gamma(H) \ge h(n) \text{ for every } H \text{ with } |V(H)| \ne 2^{n-1}Γ(H)≥h(n) for every H with ∣V(H)∣=2n−1 与对每个布尔函数 fff 的 s(f)≥h(deg(f))s(f) \ge h(\deg(f))s(f)≥h(deg(f)) 等价。对前一种 H,H 与其补图中必有一个至少含 2n−1+12^{n-1}+12n−1+1 个顶点;定理1.1取 h(n)=nh(n) = \sqrt{n}h(n)=n 即得 s(f)≥deg(f)s(f) \ge \sqrt{\deg(f)}s(f)≥deg(f)。