Prove that χ(G) ≤ n just when there is a homomorphism from the graph G to Kn I would be very grateful for help with this proof:
"Prove that χ(G) ≤ n just when there is a homomorphism from the graph G to Kn."
we know that: χ(G) ... denotes the minimum of colors needed for the vertex coloring of the graph of n vertices
Kn ... is a complete graph of n - vertices
So I divided the proof into 2 parts: a) χ(Kn) = n
since it is a complete graph of n - vertices, it is necessary to use n colors
deg(v)=n, for all v belonging to V(G) (the degrees of vertices are preserved when displayed)
So let there be a homomorphism G→Kn. Then for every vertex v of G there is exactly one vertex v′ of Kn (valid v↦v´)
it follows that the |V(G)|≤|V(Kn)| (each vertex of G must have something to display on)
further Kn has n - vertices (from the definition of a complete graph) ... it follows that G must have ≤n vertices
it follows in conclusion that the number of colors to color the vertices from G is ≤n: thus χ(G)≤n
b) Let χ(G)≤n (then the number of vertices is ≤n) ... |V(G)|≤n
further in Kn (complete graph) it is true that we have n vertices, which are all connected to each other (we must have n colors to color this graph Kn)
then there is an injective representation from G to Kn
however, I was reproached with the following:
part a) If we have homomorphism, it may not be true that |V(G)|≤|V(Kn)| and the graph does not have to have less than n vertices
part b) similarly, if we have χ(G)≤n then it may not be true that |V(G)|≤n
Note. As an example, we can take the path P on n vertices (then χ(P)=2).
Would someone please advise me how to rephrase this proof correctly, or how to go a different way ? Thank you for any advice.
 A: Why not just use the homomorphism itself.

*

*Let $f: G \mapsto K_n$ be a homomorphism from $G$ to $K_n$.


*Then [writing the vertex-set of $K_n$ as $\{v_1,v_2,\ldots, v_n\}$ ] for each $i \in \{1,2,\ldots, n\}$, the set $\{x; f(x)=v_i\}$ of vertices of $G$ mapped to $v_i$ is an independent set in $G$ i.e., for any such $i$, none of the vertices in the set $\{x; f(x)=v_i\}$ are adjacent to each other in $G$, by definition of a graph homomorphism.


*So now define a mapping $c: V(G) \mapsto \{1,2,\ldots, n\}$ as follows: for each vertex $x \in G$, set $c(x) = i$, where $i$ is the integer in $\{1,2,\ldots, n\}$ such that $f(x)=v_i$. Convince yourself that $c$ is a proper $n$-coloring of $G$. In particular, note that if $x'$ and $y'$ are vertices in $G$ satisfying $c(x')=c(y')$, then letting $i$ be the integer such that $c(x')=c(y')=i$, then $f(x')=f(y')=v_i$, and thus $x'$ and $y'$ cannot be adjacent in $G$, by 2, because $x'$ and $y'$ are both in the set $\{x; f(x) = v_i\}$. So indeed, if $x'$ and $y'$ are vertices in $G$ satisfying $c(x')=c(y')$, then $x'$ and $y'$ are not adjacent in $G$.
And then, since there is a proper $n$-coloring of $G$, namely $c$ as in 3., this implies that at most $n$ colors are needed to color $G$ or equivalently, that $\chi(G) \le n$.
