Theorem (Erdos 1947) If(份·2l-囱<1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. For a particular Kk, Pr[the Kk is monochromatic]=21-() number of Kk in Kn: () Pr[3 a monochromatic Kk] ≤（附·21- 0<1If ￾n k ⇥ · 21￾ ￾k 2 ⇥ < 1 then it is possible to color the edges of Kn with two colors so that there is no monochromatic Kk subgraph. Theorem (Erdős 1947) For a particular Kk , Pr[the Kk is monochromatic] = 21￾ ￾k 2 ⇥ number of Kk in Kn: ￾n k ⇥ Pr[￾ a monochromatic Kk ] ⇤ ￾n k ⇥ · 21￾ ￾k 2 ⇥ < 1