Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem
$$\min \|x\|_1 \quad \text{s.t.} \quad A x = b,$$
admits an $m$-sparse solution in general?
The only result that I've found so far is Theorem 3.1 in [1]. It states that if the solution is unique, then it is also $m$-sparse.
[1] S. Foucart, H. Rauhut. A Mathematical introduction to Compressive Sensing
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.
EDIT: As suggested in a comment here is a counter example:
Consider the case where $N = 2$, $m = 1$ and take $A = [1,1] \in \mathbb{R}^{1 \times 2}$. Your optimization problem becomes, take $b \in \mathbb{R}^m$ as you wish, say $3$ $$\min \|(x,y)\|_1 \quad s.t. \;\; x+y = 3,$$
In this case, you have infinitely many solutions $\{(x,y): x = 3-y, 0 \leq y \leq 3 \}$. They all have a $\ell^1$ norm equal to $3$ and yet only $2$ of them are $1$-sparse.
It is true that one can always find an $m$-sparse solution.
If $\hat x$ is solution and $\|\hat x\|_0 \ge m+1$, one can perform a small gradient step (with respect to the L1 norm) in a neighborhood of $\hat x$ restricted to vectors that have the same support and the same signs.
Let $X=\{x: \hat x_i =0\Rightarrow x_i=0, \hat x_i \ne 0 \Rightarrow \hat x_i x_i \ge 0 \}$ (same support and same signs as $\hat x$, and let $W=\{ x: Ax =b\}$ and $V = \{x: \hat x_i = 0 \Rightarrow x_i = 0\}$. The affine subspace $V \cap W$ has dimension at least $m+1 + (N-m) - N \ge 1$ hence $V \cap W$ contains at least a line. In $X\cap W \cap V$ the L1 norm is simply $\sum_j x_j s_j$ where $s_j=sign(\hat x_j)$ and we can move in the direction of the gradient of the L1 norm while staying in $X\cap V \cap W$.
Two things may happen as we move in this gradient descent direction: either we reach the boundary of $X\cap W \cap V$, or we stay indefinitely in $X$ and move towards $\infty$. The latter is not possible because moving in the gradient descent direction decreases the L1 norm. Hence we must reach the boundary of $X\cap W \cap V$.
When we reach the boundary of $X\cap W \cap V$ in this gradient direction, we have not increased the L1 norm (that's the point of the gradient descent direction), we are still in the space $W=\{x: Ax=b\}$, and reaching the boundary of $X$ means that one coordinate becomes 0 so we have decreased the sparsity of the solution by at least 1.
We can be a little more explicit. Let $h\in \text{direction}(V\cap W )\setminus \{ 0 \}$ (which always exists because $V\cap W$ contains a line) and by changing $h$ to $-h$ if necessary, assume that $\sum_j h_j s_j \ge 0$. As long as $t>0$ is small enough so that $x^t = \hat x - t h$ is in $X$, we have $$ \|x^t \|_1 = \sum_j s_j (\hat x_j - t h_j) = \|\hat x\|_1 - t \sum_j s_j h_j. $$ A solution with sparsity at most $\|\hat x\|_0 - 1$ nonzero coordinates is $x^{t_0}$ for $t_0=\inf \{t>0: s_j(\hat x_j - t h_j) > 0\}$.
