Well, I'm really happy to see you because 
if you made it that far, it basically 
means that you have successfully, you 
know, done the knapsack, you know, 
assignments and you are still willing to 
continue in the class. 
So, this is about coloring, and this is 
when things get more difficult. 
This is a very fantastic, amazingly 
beautiful assignment. 
You'll see that, okay. 
Conceptually, it's amazingly simple, 
right? 
So, we saw in the lecture, you have 
notes, you have edges between the notes. 
You want to color these things with as 
few colors as possible, okay. 
Such that two adjacent vertices are given 
a different color, okay. 
So, this is a beautiful graph. 
We've actually four nodes. 
It's a tree, so we could so optimal 
solutions very quickly, okay. 
And this is a particular solution. 
We've one node which is blue, another 
node red. 
Two green nodes, okay. 
And so we are using three colors, okay. 
So, this is what we will have to solve, 
okay. 
So this is the formalization of the 
problem, okay. 
You can look at it, okay. 
But, essentially the important things 
here is that we have a certain number of 
node and we have a certain number of 
edges, you know E. 
And that's what's going to drive the 
input of this assignment, okay. 
And we'll have a long, long, long list of 
edges because some of the problems we'll 
solve here are going to be pretty, pretty 
interesting in some societies, okay. 
So, we have a decision variable for 
everyone of the nodes and that's going to 
be the color of that node. 
That's going to be the output of this 
assignment, okay. 
So the assignment itself is basically 
minimizing the largest color that you are 
using. 
We are using numbers here, okay. 
So, you know, mini-, max, minimizing the 
maximum color that we are using, okay. 
And then we have only a single constraint 
which is reasonably easy. 
You know, two different, two adjacent 
vertices have to be given a different 
color, okay. 
So, when you look at this, you have to 
know what the input and the output are 
going to be, okay. 
So, the input here is going to have 
basically two ints, okay. 
The beginning that will tell you the size 
of the number of vertices, and then the 
number of edges, that's the two things 
that you will see there, okay. 
Number of vertices, number of number of 
edges. 
And then what you will have is a long 
list of edges, okay. 
Now an edge is basically defined by what? 
By essentially two vertices, okay. 
So, every line here that you see, the 
input is going to be basically telling 
you that there is an edge between, you 
know, the first vertex and the second 
vertex, okay. 
And, so that's basically going to be the 
input. 
So, the input is basically how many 
nodes, you know, how many, how many 
vertex, how many edges between these 
vertices. 
And then a long list of what these edges 
are. 
And that's just basically two, two 
vertices, okay. 
Now the output is going to be as usual, 
okay. 
So, what is the optimal solutions that 
you, or the best solutions that you have 
found? 
And whether it's optimal or not, okay. 
And then you will have also the colors of 
all these vertices, okay. 
So, for everyone of the vertex, you know, 
you will basically specify its color in 
the optimal well or the best form 
solution, okay. 
So, that's the basic idea, okay. 
This is a particular example, okay. 
So, you see that we have basically three 
vertices we have four vertices and three 
edges, okay. 
Those what you see there. 
And these are the various edges. 
We have an edge between node zero and 
node one, vertex zero, vertex one. 
We have another edge between vertex one 
and vertex two, and so on and so forth, 
that's what you see, okay. 
And then you see a particular of 
solutions there, which has basically 
three colors. 
And it's not proven optimal, and you see 
the various colors of these things 0122, 
okay. 
So, that's basically input. 
Very simple, long list essentially of 
edges and then the output, which is 
basically the color of every one of these 
vertices, okay. 
So, input output is very simple in this 
problem, okay. 
It's conceptually a very simple problem. 
But graph coloring is this beautiful 
property that is very very difficult to 
solve, okay. 
yeah, and this is an illustration of 
actually the two solution, the solutions 
that we just produce here. 
so let me give you some assignment tips 
here, okay. 
So, one other thing which is important 
whatever the, whatever the approach that 
you're actually using. 
Is that, you know, the degree of a node 
is important. 
The higher the degree of a node, you 
know, the more difficult it is, the more 
constrained that node is in a sense. 
You know, what the color that node can 
take is basically limited by all it's 
neighbors, okay. 
So, think about how that information can 
be exploited, okay. 
So, other things that you have to think 
about is that there are a lot and lot of 
symmetries in these problems, okay. 
So, we had a lot of lectures on 
symmetries inside the constrained 
programming lecture. 
Think about them, and think how they can 
be exploited inside this particular 
assignment, okay. 
So, what you see there is the solution 
there, okay. 
So, this is a solution, this is a 
solution which is completely symmetric, 
okay. 
You know, think about why these two 
things are symmetric. 
There is a very simple rule and, you 
know, this is essentially some of the 
techniques that we have seen in constrain 
programming there, for telling you what 
kind of symmetry this is. 
But, this can be exploited and if want or 
find actually, you know, very good 
solution and improve optimality, you will 
have to use things like this, okay. 
And then, there are other things that you 
want to do if, you know, if you want to 
improve optimality or if you want to 
find, you know, to get a, a sense of what 
your solution is. 
Try to find if they are easy lower bound 
that you can compute. 
There is one very simple conceptual lower 
bound that you can take, and that will 
tell you the best you can ever achieve, 
okay. 
So, you know, there are lot of structure 
here, although the problem is very simp-, 
you know it's very simple conceptually 
but there are lot of things that you can 
exploit and that's why I love this 
problem, okay. 
Now this is a beautiful graph here, you 
know, this is 250 vertices, it's about 
3000 edges, okay. 
Which basically means that the density 
here the den, you know, the density of 
the edges is 0.1% compared to the full 
graph, okay. 
It's a reasonably easy answer. 
I mean it's medium difficulty. 
It's still hard to prove optimality, but 
this is not some of the most difficult, 
this is not one of the most difficult 
instance. 
Now you can imagine a bushy, you know, it 
becomes when you have 50% density, okay. 
So, that's much more complex and much 
more difficult to solve, okay. 
So, so, this is essentially, you know, 
what I wanted to tell you about the graph 
coloring assignment. 
You can be really, really creative on 
this assignment. 
It's a fantastic assignment, okay. 
And I look forward to see you compete in 
finding a high-quality solution and 
proving optimality on some of these 
instances. 
Okay, have fun, it's going to be really 
interesting.