Return to Revisions

It is well-known that a maximal number of edges in a $C_4$-free graph is $\Theta(n^{3/2})$ (since every pair of vertices is connected by at most one path of length 2, so the average square of a vertex degree is at most $\Theta(n)$; this is reached, e.g., by the incidence graph of a projective plane). Thus the conjecture fails for $H=C_4$, $T=K_2$.