How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?

3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring:

Reduction from 3-Coloring instance: adding an extra vertex to the graph of 3-Coloring problem, and making it adjacent to all the original vertices.

Following the same reasoning, 5-Coloring, 6-Coloring, and even general $k$-Coloring problem can be proved NP-Complete easily. However, my problem comes out with the underlying mathematical induction:

My Problem: What if the induction goes on to $n-1$-Coloring and $n$-Coloring problem, where $n$ is the number of vertices in the graph? I certainly know that $n$-Coloring problem can be solved trivially. So, is there something wrong with the reasoning? How to understand the reduction from 3-Coloring problem to the general $k$-Coloring one?

Thanks for any suggestions.

-

The $k$-coloring problem is usually defined only for constant $k$, so $n$-coloring doesn't make sense. For every constant $k \geq 3$, the reduction you mention works. By adding a superconstant number of vertices you can show, for example, that $(n/2+3)$-coloring is NP-complete.
The $k$-coloring problem is to color any graph. You can certainly find graphs for which $k$-coloring is trivial as well as formulas for which SAT is trivial or etc. This does not impact the complexity of the problems in general though.
"Graphs for which $k$-coloring is trivial... formulas for which SAT is trivial" - every single graph is trivial to $k$-color, every single formula to determine its satisfiability, since the solution can be hardcoded. However, SAT and 3-colorability are NP-hard. In contrast, $n$-colorability has a polytime algorithm. The OP was worried that this contradicted a proof that $k$-colorability is NP-hard for every $k$. –  Yuval Filmus Jan 1 '13 at 15:01
Yes, $k$ is constant while $n$ depends on the size of the graph. –  Yuval Filmus Jan 1 '13 at 23:02