Let us consider a 5 vertices graph,
use every edge for 4 vertices , we know number of edges possible for a 4 vertices regular graph is the complete graph k4,
we have used up 6 edges, and to connect to the final vertex you need one more edge.
Thus for this graph to be connected you must use more than 6 edges {(5-1)(5-2)/2}
which on generalizing results to the formula in question.
*Equivalent statement would be , for n vertices consider edges more than required in k(n-1); which is C(n-1,2)