I am trying to answer the first part of the question.
The graph Tm,n specified in the question is a special type of graph known as Turan's graph. A Turan's graph is a complete m-partite graph where size of each partition differ by atmost 1.
No of vertices in Tm,n = n
No of partitions in Tm,n = m
Let
$n = am + b$
$n = am + b - ab + ab$
$n = b (a + 1) + (m - b) a$
So out of m partitions of Tm,n b partitions have size a+1 and m-b partitions have size a.
No of possible pairs of vertices within the same partition is
$b\binom{a+1}{2} + (m-b)*\binom{a}{2}$
So total no of possible edges in Tm,n is
$\binom{n}{2} - (b\binom{a+1}{2} + (m-b)*\binom{a}{2})$
The answer is not complete. If someone know how to continue, please suggest.
(Note that a = k = floor(n/m))