Let T be a tree with m edges, and let G be an n-vertex graph with more than $n(m − 1) − {m\choose 2}$ edges. Prove that T is a subgraph of G.
It seems clear that the question is missing a bit of information its clear that $n\geq m+1 $
The problem i am having is lets assume that $n=m+1$ then we have $(m+1)(m-1)-(m^2 -m) = m^2-m +m -1 -m^2+m=m-1$ now it does say more than so i guess you could argue that G has m edges but its clear that the statement isn't true in this case just pick G to be any tree that is not T and the result follows.
Any idea what this is actually saying?
Edit: NVM $m=1$ is ok because it says that G has more than 0 edges ie it has at least 1 edge. That is it says $|E(G)|> n(m-1)- {m \choose 2} $
Assume the statement for some $m\geq1$. Let $G$ be a graph with $|E|> (m+2)((m+1) − 1) − {m+1 \choose 2}$ and $T$ a tree with $m+1$ edges. The degree of any vertex in $G$ is at most $|V|-1$, so if $G'$ is a subgraph of $G$ obtained by removing a vertex, $$|E'|> (m+2)((m+1) − 1) − {m+1 \choose 2}-((m+2)-1)$$ $$|E'|> m(m+2) - {m+1 \choose 2} -m-1 $$ we WTS that $$|E'|> m^2-1 +m - {m+1 \choose 2} \geq (m+1)(m-1) - {m\choose 2} $$ $$ m - {m+1 \choose 2} \geq - {m\choose 2} $$ $$0\geq 0 $$
Therefore if $T'$ is a subgraph of $T$ obtained by removing an edge, there is a subgraph $S'$ of $G'$ with $S'\cong T'$. Since the vertex removed from $G$ was arbitrary, it follows that there is a subgraph of $G$ congruent to $T$.