that was first popularized by Al Cohen of York, who was an anglo-saxon

really smart dude. The problem is: you have a farmer who comes to your river and with him he has a wolf,

a bundle of cabbages and a goat; and there's a boat,

that's there and it carry-- it can carry him, and

one of his charges. Obviously the farmer has to be there because he has to be rowing,

and he wants to bring everything to the other shore safely. So that means that he cannot leave

the cabbage with the goat, because the goat would be eating the cabbage,

and he cannot leave the wolf with the goat because then the

wolf would eat the goat. So how can he do it?

And so of course we're assuming that the wolf cannot swim

which is a question I get all the time, when I'm speaking

to kids. So the wolf cannot swim neither can a goat or the cabbage.

So the only thing you can do at first is to

bring the goat.

Okay, so then, okay, the farmer goes back,

and he--

takes, let's say, the wolf; but now he cannot leave the wolf with the cat--

with the goat. Otherwise the wolf would eat the goat back. So what if he brown the cabbage instead?

Well, same thing if he brings the cabbage now,

the goat would eat the cabbage. So the only way it can be done

is you have to have this clever moment of saying "Oh, I can bring back the goat". So, okay,

he brown the cabbage over

and now he brings back the goat, and now takes the wolf, brings it to the other side as well,

and now he goes back just to get his goat. So...

Then you can generalize, you can say "Well, Let's say that this farmer had more things

that he wanted to carry across the river".

So let's say that I added a rabbit, so

What can I do first?

Brady Haran: What does a rabbit day with what?

Oh.

Brady Haran: Who is in danger from who here?

Yeah good question right, so the wolf would eat the rabbit,

and...

Ah well the rabbit would eat the cabbage.

We assume that the rabbit and a goat together are fine.

There won't be too much violence there. The boat can hold the farmer and

one of these guys. That's it, the farmer still has to be there.

We're still assuming also that the revit cannot swim. So what can I bring first?

Can I bring the wolf? Well, no obviously the rabbit and the goat would eat the cabbage.

Can I bring the rabbit?

Well, no again the goat would eat the cabbage, if the wolf doesn't catch the gold first.

Okay, can I bring the goat? Well,

no, the rabbit will eat the cabbage again,

if the wolf doesn't catch the rabbit first.

And can I bring the cabbage? No, because the wolf would eat the rabbit and the goat.

Brady Haran: Carnage.

Carnage, yes. Blood everywhere no matter what we do

or shreds of cabbage, one or the other. So the question becomes: Okay,

How big of a boat do I need? So if I'm given

different things, and I know there's certain conflicts how big does my boat have to be? So here if I have space for

my farmer plus two other things, I'll be fine. I could just say fine, I'll bring the wolf and cabbage first

I'll leave them on the other side, come back, and get my rabbit and goat

and I will be done.

Super easy!

So the question is how big does it have to be? Well, now we kind of want to start doing math, right?

So how do we bring math in there? So we want to think about the conflicts as making a graph. So I have my--

wolf, and I have my goat; and so I cannot leave my wolf with my goat

so I'll put an edge, the line, between these two points which are really

normally called "vertices".

Brady Haran: So edge represents bad news.

Yeah conflict, that these two things cannot be left alone unsupervised.

The wolf can also not be left

with the rabbit. The goat cannot be left with the cabbage and the rabbit cannot be left

with the cabbage either.

But the wolf can be left with a cabbage so I don't draw an edge there,

and I don't draw an edge between my goat and my rabbit because it can be left together.

Okay, the point that we see is that let's say that I first took my rabbit, well,

there's still some lines remaining, right? I am left with a

graph with the wolf, goat and cabbage and there's still some lines that are remaining.

And that's tree firing remove any of the corners.

So what I want to do is

take a set of my things, that will remove all of the lines, and that's actually a really important math concept.

It's called a "vertex cover".

So, maybe let's write down, what is the vertex cover. "A vertex cover and

a graph G is a set of vertices such that any edge is

adjacent to at least

one

of these services". Okay,

so what does that mean? That means that

if I want to take a set of points, where

every line is touching at least one of these points, my goal is that by taking the vertex cover,

I'm removing all the lines so maybe we can just draw a simple example.

So, let's say that I have this graph.

So, this is a graph so a graph is really just a set of points and set of lines called vertices and edges,

and so I might ask myself "What is a vertex cover?" So I could start building one. So I could say "Okay

I'll take this vertex within my

vertex cover".

But that's not enough, right? So these five edges now are covered by this vertex right they're touching...

this vertex, but the other ones aren't yet.

Now so I could ask "I could add this vertex to my vertex cover, and so I'm getting closer".

But I still have this line that is not covered yet.

So I could add this one now. And so these three vertices from a vertex cover

every single line is adjacent to one of these vertices.

Brady Haran: It's almost like how many hands did you need to cover the right number of spots?

Yeah exactly, exactly.

So here in a vertex cover...

What was it? Well, yeah one is not sufficient, right?

A single vertex is not a vertex cover. If I cover the rabbit and the goat,

then they're covering all of the

edges. There's no edges remaining so this forms a vertex cover.

So that's why I need to have at least

two seats, because the minimum size of a vertex cover in there is 2. So there's no way that I can do it if I

don't have at least two extra places besides the place for the-- farmer. So in general

I know that my boat has to have at least the minimum size of a vertex cover.

Right? Otherwise

I won't be able to make my first trip, because there will be some lines remaining in my graph,

And lines represent conflict.

Brady Haran: I imagine you could do overkill though,

there must be as these things get more complicated. There must be--

vertex covers that cover too many vertices.

Oh yeah, that's a really good point, right? So in this graph for example--

So if I add this vertex, this is still a vertex cover,

right? So, I really want the minimum one. So I want to say that the

"number of

extra places

needed in my boat is at least the

size of the minimum vertex cover". So in this graph here that was three.

I needed to have at least three--

Brady Haran: Because that final the smallest possible.

Yeah, you don't want to overkill as you said. So that's nice, but now you might ask yourself: Will that always be enough?

Right? Like-- Sure you can do the first trip across the river,

but will you be able to do all of them? And so now you could check with some examples.

So, I mean, we could try with a big example and see if it works out,

and then...

Try with some other examples. Does that sound good? Okay,

so maybe we need another piece of paper. Okay

so now we have way more things. And so now we need to think for a second, what is actually going to eat what.

And we might disagree on some of these. I am NOT a farm girl

So I would go with what I think. The wolf would eat the goose.

Potentially, the mouse if it's really hungry. Told eat grass.

It... won't eat the cat either, I don't think so. Carrot or cabbage

It's not a vegetarian. It's a carnivore so set a goat and the rabbit; and the goose will eat

Ahhh... the grass, I see geese eating grass all the time. I don't think it's gonna eat carrot or

cabbage because it doesn't really have-- does it have teeth?

Does I don't think... I mean certainly if it's not cut up,

you know, like it will have trouble it doesn't have hands to--

Brady Haran: Maybe this does not the taste of cabbage.

Fine. I think the mouse will eat carrot,

and...

the cabbage and...

the cat will eat the mouse, certainly.

The grass will probably be eaten by the goat. I know that you can use them as long Moore's. The rabbit might eat some grass?

Cat I think it will just eat the mouse and nothing else will eat it

Brady Haran: The rabbits gonna eat the carrot

Yes, so the cabbage yeah, that's true.

So the rabbit will eat the carrot and the goat will probably eat the carrot too,

and the rabbit will also eat the cabbage, and so will the goat,

and then the goat and a rabbit are fine. I think that's that looks reasonable to me.

Brady Haran: Okay that will be air I guess...

Do you agree? Okay, so let's say that I have a river

How big it boat we need, and will the minimum vertex cover be enough? The first point

I really want to make is that finding the minimum vertex cover is not easy.

Right. So, here we only have nine things. right? It's not that much, and to figure out

what it is, well since this graph has some meaning,

I'm going to use the meaning to help me. So I basically have like my carnivores, my herbivores,

and then I have the poor vegetables and herbs. And so these three categories

kind of help me determine that oh, maybe

the

goat rabbit

goose and mouse. So my herbivores might form a vertex cover, and I think if I look at it,

carefully, like if I were to really look at every single

line, so actually yes, the mouse the goose the rabbit and a goat do form a vertex cover

It's unclear if that is actually the smallest, I claim it is.

It's not an actually such an easy thing to check, so let's just assume that I'm right. So what I'll do is

I'll say: Okay for my first trip, I will take my minimum vertex cover.

Right? So if I remove my goat, rabbit, boots and mouse;

and bring them to the other side. I am left. I removed all of the lines, here,

and so, okay, that's fine.

So then my farmer will come back.

We can only take four things, it will leave a thing behind. Let say it leaves the cat behind

And so he brings these guys.

But certainly the wolf will attack these guys, and these guys will eat all of the vegetables and grass.

So I'll bring them back

So it's the same trick as we've seen before. I'll carry my cat over so that it doesn't eat my mouse just itself, right?

It's just four places, but you can just bring one thing. That's completely fine.

And then I will finally go back, so there's no conflict here. All right this was the

original things that I had left at first so no problem there, and then I'll bring my four leftover...

herbivores and leave them there.

And I'm done!

So I succeeded in this case, right? But that's not a proof, right? Maybe...

Maybe I wouldn't need more, and certainly We've just seen okay finding your minimum vertex Cover is not necessarily so easy

So maybe let's do one other example.

So let's say that I had just--

my wolf

and--

my--

four herbivores that would get eaten by my wolf.

If he has a chance. So my wolf would eat all of these,

and none of these would attack each other, right? So I have my river

So, I know that I need to have at least... The number of extra places should be at least the size of

my minimum vertex cover, which here is easy to calculate. What is it Brady? Do you know?

Brady Haran: It's one.

It's one...

Brady Haran: You should ... the wolf

I'm very impressed. Okay, so my wolf is my minimum vertex cover, so I need to bring my well first, right?

That's the only thing I can do if I bring anything else. I'll be left with some conflict. So I bring my wolf over.

I Come back as I can only take one thing

So let's say that I take the mouse.

But they all really look the same, like the graph all looks the same for all of them,

and these are cold different things, but it could have been called--

you know goat one, goat two, goat three and goat four. Really, so I bring my mouse over

So now I have no choice, but to bring the wolf back, right? Otherwise my wolf would eat my mouse

So... I bring the wolf back...

and then, well, I'm kind of stuck, right? So either I bring one of these guys.

But then my wolf would eat the two remaining guys.

Or I bring the wolf again, and I keep going like this, and I'm stuck.

Okay--

Brady Haran: Minimum vertix cover doesn't work.

It doesn't work. It doesn't work.

So how much do you need how much bigger does it have to be?

And the amazing thing is, you just need one more! at

Whatever the graph of conflicts is

You will only need at most one more than your minimum vertex cover. And so the way to do it, is very simple

You have these

conflictual things that, you know, like, like your wolf here.

So you just put all these conflictual indivi-- individuals in the boat with you at all times.

So you can watch them, and then one by one you carry everything else. So here

Okay, my minimum...

Brady Haran: So the wolf does every trip?

Yeah the wolf is with you the whole time. It does every trip back and forth.

So, now let's say that I have the minimum

vertex cover plus 1 seat extra, so I have 2 seats plus a farmer's seat. So I'll take my