Revision as of 06:21, 3 March 2016 edit Baking Soda (talk \| contribs) Extended confirmed users 5,570 edits →Second example: fix — ← Previous edit		Revision as of 22:00, 10 April 2016 edit undo Hamsterrific (talk \| contribs) 2 edits m Changed "color the edges" link to a more precise wikipedia page Tag: Visual edit Next edit →
Line 18: ===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 [[~~Graph~~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