Sorry for the english, I tried to make it the most clear possible.
Be $G$ a connected graph not directed, I have to find an algorithm that given $n$ the quantity of vertex and $0<k<n$ disjoint components gives a graph such the weight of it's maximum edge is the minimum possible. Then, proof that this algorithm is correct.
So the algorithm I came up with is:
First whit some known algorithm, generate the minimum spanning tree. (for example whith the prim algorithm)
For 1 to k get the maximum edge of this Minimum spanning tree and delete it.
done.
Proof that this work:
By induction:
Base Step($k=1$) :
Let $G$ be our graph of $n$ vertex and connected, getting a minimum spanning tree of $G$, we know we have a subgraph such all the vertex are connected there are no circuits and the sum of the weights of the edges is minimum.
If the sum of the weights of the edges is minimum, then this means the maximum weight of an edge is minimum. Then this step holds.
Inductive step(if $i-1 \rightarrow i$):
Let $G'$ be the minimum spanning tree. By Inductive hypothesis I know i can get the firsts $i-1$ edges and I get the disjoint graph the maximum weight of an edge is minimum for $i-1$ connected components. Then deleting the maximum weight edge, I get the disjoint graph the maximum weight of an edge is minimum for $i$ connected components.
I'm not very convinced this proof is correct, the inductive step feels very rare, and I think I used it wrong.
What do you think?