B5

Part of 1956 Putnam

Problems(1)

combi proof without induction

Source: Putnam 1956/B5

Show that a graph with 2n points and

n^2 + 1

edges necessarily contains a 3-cycle, but that we can find a graph with 2n points and

n^2

edges without a 3-cycle.
please prove it without induction .

combinatoricsgraph theoryTuran s theorem