Is the probabilistic method better than a mere counting argument? When reading proofs in the probabilistic method, it always seems like magic to me: Why should we invoke a probabilistic argument to prove facts about discrete objects?! So I decided to try to replace the probabilistic argument with a simpler counting argument. 
To be concrete, consider the first example in the Wikipedia page: there is a complete graph on $n=5$ vertices, and we wish to show that it is possible to color its edges in two colors so that there is no complete subgraph on $r=4$ vertices which is monochromatic.
My counting argument is the following:


*

*The total number of $r$-subgraphs is ${n \choose r}$.

*Each $r$-subgraphs has ${r \choose 2}$ edges and thus can be colored in $2^{r \choose 2}$ different ways.

*Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).

*Hence, the total number of colorings that are bad for all subgraphs is at most $2 {n \choose r}$.

*Since $2^{r \choose 2} > 2 {n \choose r}$ for the numbers chosen, there must be at least one coloring which is not 'bad' for any subgraph.


This counting proof is very similar to the probabilistic proof, but it is simpler because it does not require any knowledge of probability definitions and theorems (such as the theorem about the expectation of the sum of random variables). All it requires is counting, which is a very basic human activity, so it can potentially be understood by a larger audience.
MY QUESTION IS:   Is there a general equivalence between probabilistic-method and counting arguments? I.e., is it possible to convert any proof in the probabilistic method to a counting-based proof that does not use probability?
 A: The first probabilistic proof on that Wikipedia page is kind of a special case, in that the probability model it uses is "each edge exists with probability 1/2", which means the distribution on the set of labeled graphs with $n$ vertices is uniform. So rephrasing it in terms of pure counting is fairly natural.
In general (and, in fact, for the second proof on that page) your random graph model is going to select different graphs with nonuniform probability. You could rewrite this without talking about probability, but it would involve defining some kind of weight function dependent on the specific properties of a graph, and then showing that the sum of the weights of all graphs that satisfy your desired property is eventually nonzero. 
If you're using this kind of argument to show the existence of something, you probably want the weight of each graph to be non-negative (otherwise, there might be some kind of weird cancelation that prevents you from detecting what you're looking for). And if you're assigning a non-negative real-valued weight to each graph, you might as well normalize those weights and call them "probabilities", to leverage pre-existing theorems and intuition about how probability works...
