△-free→lEl≤n2/4 First Proof.Induction on n. Basis:n=1,2.trivial Induction Hypothesis:for any nN n2 1E> →G2△ 4 Induction step:for n=N due to I.H.E(B)<(n-2)2/4 7 E(A,B)川=|E-|E(B)川-1 n2_ 4 m-22-1=n-2 4 pigeonhole! Induction on n. Induction Hypothesis: for any n < N Induction step: for n = N Basis: n=1,2. trivial -free 㱺 |E| ≤ n2/4 |E| > 㱺 G ⊇ n2 4 First Proof. A B due to I.H. |E(B)| ≤ (n-2)2/4 |E(A, B)| = |E| |E(B)| 1 > n2 4 (n 2)2 4 1 = n 2 pigeonhole!