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.