(I have no idea what happened in this case, and I'm not saying a spoken agreement is necessarily a contract or that you definitely can offer any given piece of evidence to prove it. The rules are complicated. But contract law is basically about fairness, not technicalities. If "you have no legal proof!" sounds unfair, that's a good hint that it's probably not an accurate statement of the law.)
Just because the idea is kind of neat: It's possible you're getting jumped on by the lawyers here because "legal proof" itself is such a non-legal concept. There's such a thing as mathematical proof, for sure. There might be such a thing as scientific proof. But you could rarely point at something and say "that's legal proof." You could only say, "that turned out to be enough evidence to convince that particular jury." "Proof" is defined by the observer (jury, judge, etc.), not the object (contract, bloody knife, etc.).
He did have a contract. It just wasn't written and signed. It's still a contract. The CFO is misleadingly implying that because it was not signed, there was no contract.