Approver does not receive a Email notification

I have set up triggered an Approval Cycle. However, the Approver complains he has not received any Email notification from the System. Note that I have received a notification that the approval cycle has been triggered.