The Dimension Bound for Graph Algebraic Immunity Is Attainable

Let the graph algebraic immunity of a Boolean map f:F_2^n -> F_2^m be the least degree of a nonzero reduced Boolean polynomial vanishing on its graph. We prove that the dimension bound, the least d with sum_{j=0}^d binomial(n+m,j)>2^n, is attained for every n,m>=1. Translation invariance gives a rank-density inequality for every subset of the Boolean cube. Rado's classical independent-representative theorem, applied after adjoining dummy vectors, yields a basis using distinct input fibres. Completing those points to a graph proves the result. The proof is self-contained and answers the unrestricted existence question in Oberwolfach Report 31/2007. No balancing, permutation, or additional cryptographic property is imposed. Exact finite certificates accompany the argument. This is an unrefereed preprint using classical matroid tools, with no absolute priority claim.