Backups need to serve two purposes. They should protect you from hardware failures, but they should also protect you from user mistakes. A single point in time backup can't protect you from the latter, because if you make a mistake, and then a backup occurs, you're screwed. That's why Time Machine is so great. But if certain data is important it's important to keep multiple copies on multiple media. Even Time Machine is worthless if the drive it's on fails.
I'm really not being critical. I'm sorry your wife's pictures seem to be gone. I just wanted to comment so future readers might be motivated to learn from this unfortunate experience.
One hopeful thought...iCloud might take some time to update after a change of 4000 photos. In a few hours or days, they might just show up in Recently Deleted. Crossing my fingers for you...