# Why does vector potential $\mathbf A$ satisfy $\mathbf E = -\nabla \phi - \frac{\partial \mathbf A}{\partial t}$?

As any magnetic field $$\mathbf{B}$$ is divergence-free i.e. $$\nabla\cdot \mathbf B = 0,\tag{1}$$ by the solenoidal theorem there exists a vector potential $$\mathbf A$$ that satisfies $$\mathbf B = \nabla \times \mathbf A.\tag{2}$$ However, Wikipedia states an additional constraint for the vector potential, that is

$$\mathbf E = -\nabla \phi - \frac{\partial \mathbf A}{\partial t}\tag{3}$$ where $$\phi$$ is the electric potential. How does this constraint arise? Can we derive it from the Maxwell-Heaviside equations?

This is not actually a constraint on $$\mathbf{A}$$, rather a way of calculating the electric field from it.
Maxwell's equations are \begin{align} \begin{gathered} \nabla\cdot\mathbf{E}=\frac{\rho}{\epsilon_0} &\qquad \nabla\cdot\mathbf{B}=0\\ \nabla\times\mathbf{E}=-\frac{\partial\mathbf{B}}{\partial t} &\qquad \nabla\times\mathbf{B}=\mu_0\mathbf{J}+\mu_0\epsilon_0\frac{\partial\mathbf{B}}{\partial t} \end{gathered} \end{align} As you said, $$\nabla\cdot\mathbf{B}=0$$ implies that there exists some vector potential $$\mathbf{A}$$ which satisfies $$\mathbf{B} = \nabla\times\mathbf{A}$$. This is the only condition which $$\mathbf{A}$$ must satisfy.
Replacing $$\mathbf{B}$$ with $$\nabla\times\mathbf{A}$$ in the third equation gives $$\nabla\times\mathbf{E}=-\frac{\partial}{\partial t}(\nabla\times\mathbf{A}) = -\nabla\times\left(\frac{\partial \mathbf{A}}{\partial t}\right)$$ so that $$\nabla\times\left(\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t}\right) =\mathbf{0}.$$ This means that $$\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t}$$ may be written as the gradient of some scalar field $$\phi$$, i.e. $$\mathbf{E}+\frac{\partial \mathbf{A}}{\partial t} = -\nabla\phi.$$ This potential formulation is extremely useful and turns out to be very fundamental.
OP's eq. (3) can be viewed as a (local) definition of the electric potential $$\phi$$ since Faraday's law implies that the vector field $$\mathbf{E} + \frac{\partial \mathbf{A}}{\partial t}$$ is rotation-free, and hence (locally) a gradient field $$-\nabla\phi$$. See also this Phys.SE post for a manifestly Lorentz-covariant formulation.