The Fibonacci sequence $F_n$ is defined by $F_1=F_2=1$ and the recurrence relation $F_n=F_{n-1}+F_{n-2}$ for all integers $n\geq3$.

Let $m,n\geq1$ be integers. Find the minimal degree $d$ for which there exists a polynomial $f(x)=a_dx^d+a_{d-1}x^{d-1}+\dots+a_1x+a_0$, which satisfies $f(k)=F_{m+k}$ for all $k=0,1,...,n$.
1. **Define the Fibonacci sequence and the problem:**
   The Fibonacci sequence \( F_n \) is defined by \( F_1 = F_2 = 1 \) and the recurrence relation \( F_n = F_{n-1} + F_{n-2} \) for all integers \( n \geq 3 \). We need to find the minimal degree \( d \) for which there exists a polynomial \( f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0 \) that satisfies \( f(k) = F_{m+k} \) for all \( k = 0, 1, \dots, n \).

2. **General polynomial interpolation:**
   To find a polynomial with given values \( f(0), f(1), \dots, f(n) \), we generally need a polynomial of degree \( n \). This is shown by methods such as Lagrange Interpolation or the non-vanishing of the corresponding Vandermonde determinant.

3. **Criterion for polynomial degree:**
   We use the following lemma to determine when given numbers \( f(0), \dots, f(n) \) are values of a polynomial \( f \) of degree strictly less than \( n \):
   \[
   0 = \sum_{j=0}^d \binom{d}{j} (-1)^j f(j) = f(0) - \binom{d}{1} f(1) + \binom{d}{2} f(2) - \dots \pm f(d).
   \]
   For example, four numbers \( a, b, c, d \) are successive values of a quadratic polynomial if and only if \( a - 3b + 3c - d = 0 \).

4. **Application to Fibonacci numbers:**
   We need to study numbers \( m, n \) for which
   \[
   \sum_{j=0}^n \binom{n}{j} (-1)^j F_{m+j} = 0. \quad (*)
   \]
   If this is not satisfied, the smallest possible value of \( d \) is \( d = n \). If it is satisfied, the minimal value of \( d \) is smaller.

5. **Expressing Fibonacci numbers in terms of \( F_m \) and \( F_{m+1} \):**
   Using the identity \( F_{m+j} = F_j \cdot F_{m+1} + F_{j-1} \cdot F_m \), we can express the left-hand side of \( (*) \) as:
   \[
   F_{m+1} \cdot \left( \sum_{j=0}^n \binom{n}{j} (-1)^j F_j \right) + F_m \cdot \left( \sum_{j=0}^n \binom{n}{j} (-1)^j F_{j-1} \right).
   \]

6. **Evaluating the sums:**
   The sums in the brackets do not depend on \( m \). By induction or using the Cauchy-Binet formula, we can show that:
   \[
   \sum_{j=0}^n \binom{n}{j} (-1)^j F_j = -F_n \quad \text{and} \quad \sum_{j=0}^n \binom{n}{j} (-1)^j F_{j-1} = F_{n+1}.
   \]

7. **Simplifying the identity:**
   Substituting these results into the expression, we get:
   \[
   F_{m+1} (-F_n) + F_m F_{n+1} = 0 \implies F_{m+1} F_n = F_m F_{n+1}.
   \]
   This simplifies to \( m = n \).

8. **Conclusion:**
   The value \( d = n \) is always possible. A smaller value of \( d \) is possible if and only if \( m = n \). In that case, the smallest possible value of \( d \) is \( d = n - 1 \).

The final answer is \( \boxed{ d = n } \) for \( m \ne n \) and \( d = n - 1 \) if \( m = n \).