How do I prove that the MSE is zero when all predictions are equal to the corresponding labels?
This is very easy to prove.
Let's first prove that, if $\hat{y}_k = y_k$, then the $E = 0$. I will leave all steps, so that it's super clear.
\begin{align}
E
&amp;=\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2 \\
&amp;=\frac{1}{2}\sum_k(y_k - y_k)^2\\
&amp;=\frac{1}{2}\sum_k(0)^2\\
&amp;=\frac{1}{2}\sum_k 0\\
&amp;=\frac{1}{2} 0\\
&amp;=0\\
\end{align}
To prove the other way around, i.e. if $E = 0$, then $\hat{y}_k = y_k$, you can do as follows
\begin{align}
\frac{1}{2}\sum_k(\hat{y}_k - y_k)^2 
&amp;=E\\
&amp;=0
\end{align}
Recall now that any number squared is non-negative (i.e. positive or zero). Given that $(\hat{y}_k - y_k)^2 $ is non-negative, then $\sum_k(\hat{y}_k - y_k)^2$ is a sum of non-negative numbers. The only way that a sum of non-negative numbers is equal to zero is if all numbers are zero, so we must have $\hat{y}_k = y_k$ (because any non-zero number squared is non-zero).
(Note that $E$ is the mean squared error, i.e. a loss function, and it's not the back-propagation algorithm, which is just the algorithm that you use to compute partial derivatives of $E$ with respect to the parameters of the model, which are not even visible in the way you wrote $E$).