Can you fill the following python code such that it passes the three tests I give you?

Python code:

from pulp import $*$

def encode$\_$and$\_$solve$\_$three$\_$coloring$($n$,$ edge$\_$list$)$:

assert n $>=1,$ 'Graph must have at least one vertex'

assert all$(0<=$ i and i $<$ n and $0<=$ j and j $<$ n and i $!=$ j for $($i$,$j$)$ in edge$\_$list $),$ 'Edge list is not well formed'

prob $=$ LpProblem$(\text{'}$Three Color', LpMinimize$)$

#$1.$ Formulate the decision variables

#$2.$ Add the constraints for each vertex and edge in the graph.

#$3.$ Solve and interpret the status of the solution.

#$4.$ Return the result in the required form to pass the tests below.

# your code here

raise NotImplementedError

Test $1$:

n $=5$

edge$\_$list $=[(1,2),(1,3),(1,4),(2,4),(3,4)]$

$($flag$,$ color$\_$assign$)=$ encode$\_$and$\_$solve$\_$three$\_$coloring$($n$,$ edge$\_$list$)$

assert flag $==$ True, 'Error: Graph is three colorable but your code wrongly returns flag $=$ False'

print$($f$\text{'}$Three color assignment: $\{$color$\_$assign$\}\text{'})$

def check$\_$three$\_$color$\_$assign$($n$,$ edge$\_$list, color$\_$assign$)$:

assert len$($color$\_$assign$)==$ n$,$ f'Error: The list of color assignments has $\{$len$($color$\_$assign$)\}$ entries but must be same as number of vertices $\{$n$\}\text{'}$

assert all$($ col $==\text{'}$r$\text{'}$ or col $==\text{'}$b$\text{'}$ or col $==\text{'}$g$\text{'}$ for col in color$\_$assign$),$ f'Error: Each entry in color assignment list must be r$,$ g or b$.$ Your code returned: $\{$color$\_$assign$\}\text{'}$

for $($i$,$ j$)$ in edge$\_$list:

ci $=$ color$\_$assign$[$i$]$

cj $=$ color$\_$assign$[$j$]$

assert ci $!=$ cj$,$ f$\text{'}$ Error: For edge $(\{$i$,$j$\})$ we have same color assignment $(\{$ci$,$ cj$\})\text{'}$

print$(\text{'}$Success: Three coloring assignment checks out!!$\text{'})$

check$\_$three$\_$color$\_$assign$($n$,$ edge$\_$list, color$\_$assign$)$

print$(\text{'}$Passed: $10$ points!$\text{'})$

Test $2$:

n $=5$

edge$\_$list $=[(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]$

$($flag$,$ color$\_$assign$)=$ encode$\_$and$\_$solve$\_$three$\_$coloring$($n$,$ edge$\_$list$)$

assert flag $==$ False, 'Error: Graph is NOT three colorable but your code wrongly returns flag $=$ True'

print$(\text{'}$Passed: $5$ points!$\text{'})$

Test $3$:

n $=10$

edge$\_$list $=[(1,5),(1,7),(1,9),(2,4),(2,5),(2,9),(3,4),(3,6),(3,7),(3,8),(4,5),(4,6),(4,7),(4,9),(5,6),(5,7),(6,8),(7,9),(8,9)]$

$($flag$,$ color$\_$assign$)=$ encode$\_$and$\_$solve$\_$three$\_$coloring$($n$,$ edge$\_$list$)$

assert flag $==$ True, 'Error: Graph is three colorable but your code wrongly returns flag $=$ False'

print$($f$\text{'}$Three color assignment: $\{$color$\_$assign$\}\text{'})$

def check$\_$three$\_$color$\_$assign$($n$,$ edge$\_$list, color$\_$assign$)$:

assert len$($color$\_$assign$)==$ n$,$ f'Error: The list of color assignments has $\{$len$($color$\_$assign$)\}$ entries but must be same as number of vertices $\{$n$\}\text{'}$

assert all$($ col $==\text{'}$r$\text{'}$ or col $==\text{'}$b$\text{'}$ or col $==\text{'}$g$\text{'}$ for col in color$\_$assign$),$ f'Error: Each entry in color assignment list must be r$,$ g or b$.$ Your code returned: $\{$color$\_$assign$\}\text{'}$

for $($i$,$ j$)$ in edge$\_$list:

ci $=$ color$\_$assign$[$i$]$

cj $=$ color$\_$assign$[$j$]$

assert ci $!=$ cj$,$ f$\text{'}$ Error: For edge $(\{$i$,$j$\})$ we have same color assignment $(\{$ci$,$ cj$\})\text{'}$

print$(\text{'}$Success: Three coloring assignment checks out!!$\text{'})$

check$\_$three$\_$color$\_$assign$($n$,$ edge$\_$list, color$\_$assign$)$

print$(\text{'}$Passed: $5$ points!$\text{'})$