  We show that existence of a global polynomial Lyapunov function for a
homogeneous polynomial vector field or a planar polynomial vector field (under
a mild condition) implies existence of a polynomial Lyapunov function that is a
sum of squares (sos) and that the negative of its derivative is also a sum of
squares. This result is extended to show that such sos-based certificates of
stability are guaranteed to exist for all stable switched linear systems. For
this class of systems, we further show that if the derivative inequality of the
Lyapunov function has an sos certificate, then the Lyapunov function itself is
automatically a sum of squares. These converse results establish cases where
semidefinite programming is guaranteed to succeed in finding proofs of Lyapunov
inequalities. Finally, we demonstrate some merits of replacing the sos
requirement on a polynomial Lyapunov function with an sos requirement on its
top homogeneous component. In particular, we show that this is a weaker
algebraic requirement in addition to being cheaper to impose computationally.
