Although I know the notion of polynomial time reduction since many years, I am currently confused about the following problem.
In a reduction from 3-SAT to 3-Coloring, one constructs (in polytime) a graph $G_F$ out of a given 3-CNF formula $F$, s.t. $F$ is satisfiable if and only if $G_F$ is 3 colorable.
In order to show the above "if-part" a typical proof goes like: " If the graph is 3-colorable, then we can extract a satisfying assignment from any 3-coloring..." (This sentence is copied form Jeff Ericksons notes, so it must be correct :-) )
Even if we know that a graph is 3 colorable, it is np hard to find any proper 3 coloring. So given $P \neq NP$ this reduction can not be done in polynomial time.
I know that I am making some mistake in the argument above, but I can't currently see where I am wrong.