How to prove that a rainbow table is complete?
Rainbow tables are not complete. But some have good coverage. We estimate how many distinct hashes are covered by a rainbow tables using statistical tools.

We can build perfect rainbow tables where we throw out colliding chains. This reduces redundancy in the final table. But even in a "perfect" rainbow a certain hash can appear twice(but not in the same column) so we still need to estimate the coverage. 

As we approach full coverage it becomes more and more expensive. Because with a table with high coverage nearly anything we add would already be covered.