IANAL but a verbal agreement can be a legally binding contract.... which can be hard to prove in court.

But apparently if you have been paid for a job you agreed to do then that's considered a contract even if no documents were signed. If there are any lawyers out there please correct me.