$1.$ Defective coloring. Let $\backslash ($ G$=($V$,$ E$)\backslash )$ be a graph with maximum degree $\backslash (\backslash$triangle $\backslash ).$ A coloring $\backslash ($ d $\backslash )-$defective if each node $\backslash ($ v $\backslash )$ is allowed to have up to $\backslash ($ d $\backslash )$ neighbors with the same color as $\backslash ($ v $\backslash )($i$.$e$.,$ a proper graph coloring is $0-$defective$).$ Consider the following greedy algorithm: Each node is originally colored with the same color, say, color $1$ and the algorithm is given an allowed defect $\backslash ($ d $\backslash )$ as a parameter. In each step:

$($a$)$ Select an arbitrary node $\backslash ($ u $\backslash )$ such that $\backslash ($ u $\backslash )$ has more than $\backslash ($ d $\backslash )$ neighbors with the same color as $\backslash ($ u $\backslash ).$

$($b$)$ Then, re$-$color $\backslash ($ u $\backslash )$ with the smallest color $\backslash ($ c $\backslash )$ such that there are at most $\backslash ($ d $\backslash )$ neighbors with that color. Notice that this can be a new color; the size of the color palette is not given as a parameter to the algorithm

Show that this process gives a $\backslash ($ d $\backslash )-$defective coloring with $\backslash ([\backslash$Delta $/$ d$]\backslash )$ colors. Show that the process terminates in $\backslash ($ O$(|$E$|)\backslash )$ steps.