How do we know Euclid's sequence always generates a new prime? How do we know that $(p_1 \cdot \ldots \cdot p_k)+1$ is always prime, for $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $\ldots$ (i.e., the first $k$ prime numbers)?
Euclid's proof that there is no maximum prime number seems to assume this is true.
 A: That's not true. Euclid's proof does not conclude that this expression is a new prime, it concludes that there exists primes that were not in our original list, that lie between the $k'th$ prime and $p_{1}p_{2}...p_{k} + 1$ (including $p_{1}p_{2}...p_{k} + 1$). Among those extra primes that must exist, $p_{1}p_{2}...p_{k} + 1$ may be one of them, or it may not be. It doesn't matter, either way, there are more primes than listed in our initial list.
We have a counter example as soon as $2*3*5*7*11*13 + 1$.
A: Euclid's proof does not deduce that $\,N = 1+p_1\cdots p_k\,$ is prime. Rather, Euclid's proof deduces that $\,N\,$ is coprime to all $\,p_i,\,$ so the prime factors of $\,N\,$ cannot include any $\,p_i.\,$ But since $\,N> 1\,$ it has some prime factor $\,p\,$ (e.g. its least factor $> 1),\,$ which yields a prime $p$ distinct from all $\,p_i$
The key idea is not that Euclid's sequence $\ f_1 = 2,\,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ is an infinite sequence of primes but, rather, that it is an infinite sequence of coprimes, i.e. $\,{\rm gcd}(f_n,f_k) = 1\,$ when $\,n>k,\,$ since then any common divisor of $\,\color{#0a0}{f_n},\,\color{#b0f}{f_k}\,$ must divide 
$\ \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{#b0f}{f_k}\cdots f_{n-1}.$
Any infinite sequence $\,f_n > 1 \,$ of coprimes  yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least prime factor.  
Remark $\ $ This misunderstanding often arises from reading a proof of Euclid's result reformulated to be by contradiction (which was not used by Euclid). In one form, it can be deduced that if there are only finitely many primes $\,p_1,\ldots p_k,\,$ then $\,n = 1+p_1\cdots p_k\,$ is prime, because  $\,n > 1\,$  has no smaller prime factors. But this does not imply that $\,n\,$ is actually prime because the deduction depends on the hypothesis that there are only finitely many primes, which is false in the (actual) natural numbers $\,\Bbb N.\,$ Because the proof by contradiction  is carried out in the hypothetical universe "$\Bbb N$ with finitely many primes", one cannot apply any of its conclusions to the (actual) universe $\Bbb N.\,$ It is the nature of proofs by contradiction that one can deduce all sorts of nonintuitive results. When this occurs in a universe like $\,\Bbb N\,$ where we have very strong  intuition, it can be quite challenging to keep things straight. 
A: As others have mentioned, the proof you are referring to is probably the proof by contradiction that there are infinitely many primes. Compare with the following statement:

If there are finitely many non-square numbers, then there is a largest non-square number $n$ and so $n+2$ is a square.

One can see that the above statement is true, but that certainly does not imply that if we start with any non-square number $x$, we would get $x+2$ to be a square number!
