Te basta con que, antes de iniciar el tratamiento de tus datos con las variables $_POST compruebes que han sido creadas (que existen), y si así es pues avanzar. Esto es porque las variables con los nombres de tu formulario no se crean hasta que lo envíes por lo menos una vez, ya sea vacío o no.
Resumiendo, pon algo así
Código PHP:
<?php
if(isset($_POST['nombre']))
{
if(empty($_POST['nombre'])) //puedes poner nombre como cualquier otro, aquí tratas si está vacío.
//tratamiento
}
?> //código HTML con el formulario
Por otro lado, veo algunos fallos importantes de seguridad en tu código, posibles inyecciones de SQL (planteate que $nombre resulta ser = '','',''); y imprimir una consulta SQL de toda la tabla contactos. Actualmente es posible.
Mirate el tema de inyecciones SQL para solcuionarlo. Y además intenta usar siempre comillas simples en cosas de SQL aunque haya variables, unélas con el operador . y usando el \ para que no interprete las comillas simples como fin de sentencia.