We introduce the concept of sos-convex Lyapunov functions for stability analysis of discrete time switched systems. These are polynomial Lyapunov functions that have an algebraic certificate of convexity, and can be efficiently found by semidefinite programming. We show that convex polynomial Lyapunov functions are universal (i.e., necessary and sufficient) for stability analysis of switched linear systems. On the other hand, we show via an explicit example that the minimum degree of an sos-convex Lyapunov function can be arbitrarily higher than a (non-convex) polynomial Lyapunov function. (The proof is omitted.) In the second part, we show that if the switched system is defined as the convex hull of a finite number of nonlinear functions, then existence of a non-convex common Lyapunov function is not a sufficient condition for switched stability, but existence of a convex common Lyapunov function is. This shows the usefulness of the computational machinery of sos-convex Lyapunov functions which can be applied either directly to the switched nonlinear system, or to its linearization, to provide proof of local switched stability for the nonlinear system. An example is given where no polynomial of degree less than 14 can provide an estimate to the region of attraction under arbitrary switching. © 2013 IEEE.