
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 here1, 2, 3, 4, 5, 6and what you see

also is that each of the vertices here in this layerthe 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.