I am asked to show that if a graph $G$ of order $n$ does not contain a path of length $1\leq k \leq n$, then $G$ has at most $\frac{n(k-1)}{2}$ edges, which can happen iff $k\mid n$ and $G$ is the union of $\frac{n}{k}$ copies of $K_k$
I am given the result that for a graph $G$ of order $n$ and $1\leq k < n$, then if for all non adjacent $u,v \in V(G)$ then $d(u) + d(v) \geq k$, then $G$ contains a path of length $k$.
Given this I think I probably need to fix $k$ and use induction on $n$.
$n = k$ then $G$ does cannot contain a path of length $k =n$, so $G$ has at most all possible edges, ie $e(G) = \frac{n(k-1)}{2}, n=k\mid n$ and $G = K_k$. So all conditions are met.
Consider now $n>k$ and let $e(G)$ be maximal such that $G$ does not contain a path of length $k$.
Let $x$ be a vertex of $G$ with minimal degree, and consider $G_1 = G\left[V(G) - \{x\}\right]$
$G$ does not contain a path of length $k$ and so neither does $G_1$, so by the induction hypothesis we see that $G_1$ has at most $\frac{(n-1)(k-1)}{2}$ edges and is the union of $\frac{n-1}{k}$ copies of $K_k$.
At this point, I'm now stuck. I don't know how to proceed, and more importantly I don't know how to approach the condition that $k\mid n$. This suggests that I can't just increment value of $n$ one by one.
Should I have set up separate inductions for each part of the result, i.e. one induction for the maximal number of edges, and one for the result regarding when the maximum is attained? Additionally I can't quite see when it would be helpful to use the result that I was given.
Any help would be greatly appreciated. Thank you.
Induction: suppose that for a graph with $n$ nodes and every $k$ if G has at least $n(k-1)/2$ edges then there exists a path of length $k$. Inductive step: for a graph with $n+1$ nodes either $\forall{}v\in{}G$, $deg(v)>k/2$ in which case $deg(u)+deg(v)>k$ for all nonadjacent vertices or $\exists{}v:deg(v)<k/2$. Now $G/\{v\}$ has more than $n(k-1)/2$ edges and $n$ vertices.Now use the induction hypothesis.