So maybe you already see a pattern emerging here, but I am now going to
deviate just a little bit from this. I am now going to add 3 vertices here, 3 vertices here,
3 vertices here, 3 vertices here, so this is a total of 12 vertices.
And just so that we keep that in mind here, up here we have 8, here we have 12,
and here we have 24 in these layers here. Now how am I going to connect those?
And this is where the picture gets actually quite messy. I'm going to connect
them to all those here. So each of these 3 vertices here that I've added is connected
to 6 other vertices, so there's 6 edges going out here--1, 2, 3, 4, 5, 6--and what you see
also is that each of the vertices here in this layer--the first layer that I added--
is connected to exactly 5 vertices. So 1, 2, 3, 4, 5. And of course I deliberately
constructed this in this way, and I'm going to draw these out here in a minute.
I just want you to understand the principle. I've added these 12 vertices here in a way
such that the greedy algorithm will first take these 12 here, then it will take these 8 here,
and then it will take these 12 here. So I'm constructing my graph so that the greedy
algorithm will choose the vertices in exactly the reverse order that I am adding them
to the network. And in that way I can make that algorithm behave very, very, very badly.
You would think that theoretical computer science is a clean and not messy science,
but I think I can just show you the opposite here. But you get the principle now.
So these 24 vertices here are the first ones that I have added, and I have now added
these layers here. So I first added these 12 here, then these 8, then these 12 here
in such a way that the greedy algorithm will choose these vertices here to be in a
vertex cover and these here in a vertex cover. So the question, of course, now is,
can I add even more vertices to this so that I am still making the greedy algorithm
take my new vertices that I add? And in fact I can, but it will become really messy
to draw. So I'm more going to explain to you how I'm going to do this rather than
actually draw out every single vertex. So you see for each of the vertices
that I've added here, I've connected them to larger and larger groups of these vertices
here in the middle of those original 24, and I can continue this for a little bit by now
adding 2 vertices which would then be connected to groups of 8 down here.
So this would be connected to all over here, and then I will do the same part here.
So again I can add 2 vertices here, and I will connect them to this group of 8,
then 2 more vertices here, and I will connect them to this group of 8.
And if you want, you can of course check. It will still be such that the 6 vertices
I've now added will be the first ones that are picked by the greedy algorithm.
And then those 12, and then those 8, and then those 12.
What I can then do is I can add another 4 vertices, and this time I will look at
groups of 12. So I will add 4 vertices connected to these 12 here in the middle,
and I will add 4 vertices connected to these 12 here in the middle.
And we'll be done soon, so in case you think this gets very tedious, bear with me
for just another moment here, and we'll be done.
So we've added another 8 vertices, and again these will be the first ones picked by
the greedy algorithm. And final addition of vertices actually. I will add
another 11 vertices. And these vertices will be connected to all 24.
Now my question for you is, how large is a minimum vertex cover for this network
that I've constructed here? And remember every vertex is connected to those 24
vertices here in the middle. So please enter the size of the minimum vertex cover
here into this box.