I think that's a bit different - in the probabilistic method you show that if you randomly sample a graph (say) then the probability of it having some property

I think that's a bit different - in the probabilistic method you show that if you randomly sample a graph (say) then the probability of it having some property is > 0 - therefore there must exist some graph having the property. Theorem 7 in their paper is trying to count the number of graphs that contain a hypothetical 4-color counterexample if it exists. It's done by hitting a suitable generating function with a big analysis hammer to bound its coefficients, not by probabilistic means.