Can a graph with no triangles have more than (n^2)/4 edges?

[Oster]

1. Prove that a graph with n vertices that has no triangles has at most (n^2)/4 edges.



2.



3. Um so i was thinking maybe you start off with a complete graph and then keep deleting edges so as to remove the triangles within it or something? Or maybe by induction?

 

[tiny-tim]

Hi Oster!

Try induction (increasing the number of vertices by 1).