We can use backtracking to solve this problem. More specifically, we start at vertex 0, try out every color from 0 to k - 1, and then see if we can recursively paint the rest of the graph without any conflicting colors. We’ll create a helper function valid(graph, colors) that looks at the last colored vertex and all its neighbours to see if it conflicts with any of its neighbours (i.e. has the same color). We can skip over all uncolored vertices here.