Prove that for every tree T and integers k greaterthanorequa

Prove that for every tree T and integers k greaterthanorequalto 2 and g greaterthanorequalto 3, there exists a graph G without cycles of length up to g and such that every k-colouring of the edges of G contains a monochromatic copy of T.

Solution

From fact 1 we have that H contains a copy of T.

From fact 4 (pigeonhole) we have that |E(G)|/|V(G)||E(H)|/|V(G)||E(G)|/2|V(G)|or |E(G)|/|V(G)||E(GH)|/|V(G)||E(G)|/2|V(G)|

proof of (***)

We will write n(G) for |V(G)| and e(G) for |E(G)| and a(G) for e(G)/n(G)

If G does not contain a vertex v with d(v)<a(G), then (G)a(G) and we are done.

Otherwise we produce a graph G2 by removing a vertex v with d(v)<a(G). We get a(G2)=e(G2)/n(G2)[e(G)a(G)]/[n(G)1]=a(G)

You can repeat this procedure until you arrive at a subgraph H that has (H)a(H)a(G)