Cita: clientes : PK --> codcliente (AI)
trabajos: PK --> codtrabajo (AI)
Así no te causará problemas, en tanto no olvides poner la FK como te comentaba.
Lo de la secuencialidad de los numeros AI es total y absolutamente irrelevante. Que haya "huecos" en la numeración no tiene ninguna importancia, ya que no hacen nada. Lo único que importa es la unicidad de la PK, no su continuidad aritmética.
Sobre esto se nos ha preguntado muchísimo, y por eso están estos dos temas de las FAQs, que te recomiendo leer:
Cómo numerar secuencialmente una consulta, sin usar PK Renumerar un campo autoincremental