No. It is not true. The theorem you state "assumes" the existence and uniqueness of the solution and proves that in this case, you this particular solution cannot have more non-zero components than the number of measurements. The existence is proven under RIP (Chapter 6, e.g. Theorems 6.9 and 6.15), null space properties (Chapter 4, e.g. Theorem 4.4), incoherence properties (Chapter 5, e.g. Theorem 5.16), ... and I think that's it as of today. 

Good luck with this beautiful field!