Proficiency Assignment: K$-$Colorability

Topic: Reductions and NP$-$Completeness.

We have discussed $($or will discuss$)$ several hard problems $($all from the class of problems known as "NPComplete"$)$: Vertex Cover, Independent Set, Set Cover, SAT, $3-$SAT, Circuit$-$SAT.

A graph is called K$-$Colorable if we can assign every node in the graph a "color", using only K different colors, and such that no two adjacent nodes share the same color. The following is also an NP$-$Complete problem:

For a given graph, what is the smallest K such that the graph is still K $-$Colorable?

Your task is to reduce this problem to Independent Set. $($This will show that the Colorability problem is not too hard.$)$ Your reduction should be described in enough detail that I can use it on an example graph, and should give correct answers.

Once you have written and submitted your solution via Canvas, schedule a $10$ minute meeting with me to present it$.$

I will ask you about:

$-$ The parts of your reduction

$-$ An example of your reduction in action. $($I may provide an example graph for you to use, but you should be prepared to show me one.$)$