Revision as of 18:53, 16 February 2019 edit Citation bot (talk \| contribs) Bots 5,872,834 edits m Alter: issue. Add: citeseerx. \| You can use this bot yourself. Report bugs here. \| User-activated. ← Previous edit		Revision as of 02:52, 20 April 2019 edit undo Cycle space (talk \| contribs) 116 edits →First example: It is not that kind of edge colouring. Next edit →
Line 17: ===First example=== Suppose we have a [[complete graph]] on {{mvar\|n}} vertices. We wish to show (for small enough values of {{mvar\|n}}) that it is possible to ~~[[Edge coloring\|~~color the edges]] of the graph in two colors (say red and blue) so that there is no complete subgraph on {{mvar\|r}} vertices which is monochromatic (every edge colored the same color). To do so, we color the graph randomly. Color each edge independently with probability {{math\|1/2}} of being red and {{math\|1/2}} of being blue. We calculate the expected number of monochromatic subgraphs on {{mvar\|r}} vertices as follows:

Probabilistic method: Difference between revisions