Nondegenerate $\triangle ABC$ has integer side lengths, $\overline{BD}$ is an angle bisector, $AD = 4$, and $DC=9$. What is the smallest possible value of the perimeter?

By the angle bisector theorem (theorem 8), $AB:CB=AD:CD=4:9$. Since the sides are integers and $\gcd(4,9)=1$, $AB=4x, BC=9x$ for some positive integer $x$, and $AC=4+9=13$.
For a valid triangle we need $4x+13>9x$ and $4x+9x>13$, i.e. $1$AB=8, BC=18$, and the perimeter is $8+18+13=\boxed{39}$.