I worked for lawyers that did a lot of contract law. It can vary from state to state (in the U.S.) but the state I worked in a verbal agreement -- not even written down -- is legally binding. Proving a non-written agreement can be hard in court but that is a different issue.