Skip to main content
added 107 characters in body
Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.

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$.

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$.

This was an answer to a previous version of the question, when $H$ was not claimed to be a tree.

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$.

Source Link
Ilya Bogdanov
  • 23.7k
  • 54
  • 92

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$.