Does it say the message is sent? If so, the mail is queued and this is an issue with your smtp server, not a PHP one.
If it said it failed, than you likely haven't configured the smtp options in the php.ini. Either configure them there, or provide the configuration options as the fifth argument in the mail call.
As of PHP 5.5, the MySQL library has been officially deprecated. It is recommended to move to either MySQLi or PDO libraries for your mysql connectivity. See here for help choosing which interface you prefer: http://php.net/manual/en/mysqlinfo.api.choosing.php