△-free→lEl≤n2/4 Third Proof. A:maximum independent set a lAl independent u∈V,d,≤a dv B=V\A B incident to all edges B=IBI >0 Inequality of the arithmetic and geometric mean B s∑4≤a9s()- 4 u∈B-free 㱺 |E| ≤ n2/4 Third Proof. A: maximum independent set B = V \ A α = |A| β = |B| v ⇤ ⇥ ⌅ dv independent ⇤v ⇥ V, dv B B incident to all edges ⇥ + ⇥ 2 ⇥2 |E| vB dv = n2 4 Inequality of the arithmetic and geometric mean