I am probably being really absent minded in this case, but it says on Wikipedia that the necessary and sufficient conditions for the existence of a $k$-regular graph is that $n \geq k+1$ and $kn$ is even. I can see why $kn$ must be even, but I do not appreciate why $n \geq k+1$.
And, I have recently stumbled upon the past-paper question; Let $k$ be an even natural number, show that for every $n \geq k+1$, there exists a k-regular graph of order $n$. I really want to understand this!
On
For a vertex to have $k$ neighbors, which is required of a $k$-regular graph, there must be at least $k+1$ vertices so that there are at least $k$ other vertices. Simple as that.
As for the existence of a graph of order $n \geq k+1$, it amounts to saying that there is a set of cardinality $n$, which is something that at an introductory level is usually taken for granted. Any other conditions in that question?
EDIT: With the additional condition that the graph should be $k$-regular, we have that $kn$ is even because $k$ is; moreover, $n \geq k+1$. Hence the necessary and sufficient conditions for the existence of a $k$-regular graph with $n$ vertices are satisfied.
The necessity of those conditions is easily established. One follows from the need to have at least $k$ other vertices to connect to each vertex. The other comes from the fact that in any graph the sum of the degrees must be even. (In a $k$-regular graph, that sum is precisely $kn$.)
Sufficiency of the conditions may be shown constructively; that is, by showing how to build a $k$-regular graph given $k$ and $n$ that satisfies the conditions. (See, for example, Misha's answer.) Alternatively, one can "pass the buck" and invoke another, more general theorem. (See this answer.)
Even if the answer is well-known, I feel like a complete solution should include a construction.
For example, if $k$ is even, we may number the vertices $0, 1, \dots, n-1$, and connect each vertex $i$ to every vertex $i+j \bmod n$, where $-\frac k2 \le j \le \frac k2$. It's easy to see that this condition is symmetric and results in each vertex having $k$ neighbors, provided $n \ge k+1$.
(If $n \le k$, then different values of $j$ connect vertex $i$ to the same vertex.)
For the sake of completeness, we can also construct a $k$-regular graph if $k$ is odd and $n$ is even ($k$ and $n$ both odd being impossible by the handshake lemma). We can use the previous construction to get a $k-1$ regular graph on $n$ vertices, and then add edges from $i$ to $i + \frac n2 \bmod n$, for each $i$: a perfect matching that increases each degree by $1$.