Content deleted Content added
Fix version with counting argument for the first example |
|||
Line 47:
* Each ''r''-subgraphs has <math>{r \choose 2}</math> edges and thus can be colored in <math>2^{r \choose 2}</math> 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 some (at least one) subgraph is at most <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}}</math>.
* Hence, if <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}}
}}
| |||