SCP Required on Both Hosts

I was just trying to scp a file to a new VM that had been set up, and getting a strange error...

scp file.txt user@newvm:~
bash: scp: command not found
lost connection

Hmm... I definitely had SCP installed, what is going on? It turns out (as you can probably guess from the title) that SCP is required to be installed on BOTH ends of the connection. I was using CentOS 6 so...

yum install openssh-clients

And all was fine again! This will likely rarely happen (as it's never happened to me before). But watch out if it does!