We say a graph G = (V, E) has a k-coloring for some positive integer k if we can assign k different colors to vertices of G such that for every edge (v, w) E E, the color of v is different to the...

According to the problem in the picture, how do I Prove that 3-Color ≤p 4-Color?


Extracted text: We say a graph G = (V, E) has a k-coloring for some positive integer k if we can assign k different colors to vertices of G such that for every edge (v, w) E E, the color of v is different to the color w. More formally, G = (V, E) has a k-coloring if there is a function f : V → {1, 2, ..., k} such that for every (v, w) E E, ƒ(v) # f(w). 3-Color problem is defined as follows: Given a graph G = (V, E), does it have a 3-coloring? 4-Color problem is defined as follows: Given a graph G = (V, E), does it have a 4-coloring? Prove that 3-Color