parmenides51 wrote: In a graph with $8$ vertices that contains no cycle of length $4$, at most how many edges can there be? This is a direct application of Turan's theorem By Turan's theorem we have that the maximum number of edges is $\frac{8^2}{2}(\frac{3}{4})=24$ Example: $4-$partite graph complete with $2$ vertex in each part