Revision as of 20:15, 12 January 2013 edit Dekart (talk \| contribs) 1,344 edits removed Category:Algorithms; added Category:Approximation algorithms using HotCat ← Previous edit		Revision as of 14:16, 25 January 2013 edit undo Myasuda (talk \| contribs) Autopatrolled, Extended confirmed users, Pending changes reviewers 62,561 edits m →Probabilistic proof of Turán's theorem: added missing diacritic Next edit →
Line 98: : Any graph ''G'' = (''V'', ''E'') contains an [[Independent set (graph theory)\|independent set]] of size at least \|''V''\|/(''D''+1), where ''D'' = 2\|''E''\|/\|''V''\| is the average degree of the graph. === Probabilistic proof of ~~Turan~~Turán's theorem === Consider the following random process for constructing an independent set ''S'':

Method of conditional probabilities: Difference between revisions