River Crossings (and Alcuin Numbers) - Numberphile

Discussing vertex covers and Alcuin numbers for graphs - and a famous old puzzle. Filmed at MSRI with Dr Annie Raymond.
More links & stuff in full description below ↓↓↓
Annie Raymond: www.msri.org/p...
The Alcuin Number of a Graph: link.springer....
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumb...
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science.
Discuss this video on Brady's subreddit: redd.it/7ob1n2
NUMBERPHILE
Website: www.numberphile...
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberph...
Videos by Brady Haran
Patreon: / numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanb...
Sign up for (occasional) emails: eepurl.com/YdjL9

[@johnox2226]

"An Anglo-Saxon really smart dude" That is the best description ever, 10/10

[@yungml]

Also not applicable very often

[@paulc4629]

That's racist

[@stevethecatcouch6532]

Well, Alguin was at least smart enough to copy fro the Arab sources of the problem.

[@johnox2226]

Paul C Your name is racist

[@yvesivo]

*Anglo-Sachson

[@Hello-fb7sp]

I knew about this problem since childhood but had never thought of it in a mathematical way, this was really interesting! The Dr also explained it very well, I hope she appears more on this channel in the future.

[@Borednesss]

Dr. Annie Raymond seems pretty cool!

[@moviesmaster2399]

where can i attempt to post a proof for this problem ?????????????????? please

[@RWBHere]

It's an NP problem.

[@EaglePicking]

@@moviesmaster2399 That is probably the nerdiest pick-up line I ever heard :D

[@Dominikcos7]

that cabbage is a broccoli

[@tohopes]

BROCCOLI... is SPY!!!

[@edsiefker1301]

Broccoli and cabbage are the same species.

[@RubixB0y]

Ed Siefker, so? They're different strains so that doesn't make them interchangeable.

[@timseguine2]

They don't have to be interchangeable. The species itself is called cabbage. Broccoli is a cultivar of that species, ergo a type of cabbage.

[@RubixB0y]

Tim Seguine I thought they all came from wild mustard way back when.

[@Willzp360]

Brady I think your cabbage may, uh, be a broccoli

[@numberphile]

I know but there is no cabbage emoji! ;)

[@ragnkja]

Will Price It’s the same species, so does it really matter?

[@Lauraphoid]

Broccoli is a cabbage.

[@imveryangryitsnotbutter]

It's a Parker Cabbage.

[@OctagonalSquare]

I'm Very Angry It's Not Butter!! That's it! Somebody tell Matt!

[@KungFuBlitzKrieg]

So the moral of the story is, "Keep your friends close and your enemies closer."

[@bazoozoo1186]

...And keep the friends of your enimies away from enimies of your friends.

[@KungFuBlitzKrieg]

Haha! Yes indeed! :)

[@dan_tr4pd00r]

I thought the moral was just get a big enough boat.

[@RandomRageDude]

keep your friends close and their enemies closer.

[@osotanuki3359]

KungFuBlitzKrieg mmm... not really

[@Faramik2000]

Broccoli can't swim? You haven't seen mine

[@whitherwhence]

Faramik2000 Um, they're talking about cabbage

[@diek_yt]

Eyyy. Sadnecessary?

[@JoshGroach]

They talk about cabbage, but they SHOW broccoli.

[@connortremblay1259]

Just built different

[@Triantalex]

??.

[@rostfleck79]

I can't believe you missed the opportunity to say "We're gonna need a bigger boat!".

[@jmchez]

+1,000

[@gorillaau]

Some one has jumped the shark.

[@tr3ndkiller]

My jaw's dropped ...

[@KasabianFan44]

?

[@Triantalex]

??.

[@diaz6874]

But what if the farmer can eat the boat?

[@reflex5729]

El Díaz in this situations you’ve to take goat on the boat that goat will check him out

[@LokiClock]

Who boats the boaters at the boaters' exhibition?

[@RWBHere]

LokiClock, the person wearing the boater would do that.

[@DouglasZwick]

I knew it was a mistake to leave that farmer unsupervised

[@limitingchaos]

Turns out the boat, and everything else, is a spherical cow.

[@feliciabarker9210]

I'd really like a follow-up video that dug into how you DO check if a vertex cover is the minimum size

[@GeekyNeil]

10:00-10:10 Any vertex cover of this graph needs 4 vertices because there are 4 non-intersecting edges. Cat-Mouse, Goat-Carrot, Rabbit-Cabbage and Wolf-Goose. You need at least one vertex from each of those edges, so you need at least 4 vertices.

[@michaelzumpano7318]

I have seen the first problem before but never the generalization to a vertex cover plus one. Nicely done Dr Raymond. I’d like to see more videos on the application of graph theory. Any relationship to Hamiltonian path, partition or Ramsey theory would be fun too.

[@hellocollegejason198]

Goats can be lawnmowers, not a quote I was expecting on this channel.

[@Gold161803]

hellocollegejason198 At least not from anyone other than Cliff.

[@ccgarciab]

You can actually hire a pack of goats (how are those called?) to mow your grass. I read somewhere that thats what google does in their googleplex.

[@jessesantana8408]

I was entranced by Dr. Raymond I could listen to her teach for years.

[@dm551]

kzbin.info/www/bejne/o17Xqpt7jcR_l6c

[@jessesantana8408]

dm551 thank you wonderful stranger! Hope you have a nice day :)

[@RalphDratman]

Excellent. Annie Raymond is a fantastic explainer and teacher!

[@soulstealer29a]

From the thumbnail I thought we were summoning a really cute demon.

[@Sionweit]

hahaha

[@ObjectsInMotion]

I mean the venn diagram of satanists and graph theorists IS a circle...

[@miteshgurav6069]

Anthony Khodanian The math is strong with this one!!

[@Ghostofchristmasfuture]

You can try to summon a demon with any shape you want it will Probably have the same result.

[@omikronweapon]

I'd try a penciltangle, to summon a cute nerdy demon.

[@Frosty-oj6hw]

This channel is like a never ending fountain of attractive, nerdy, maths goddesses.

[@camilohiche4475]

Instant platonic crush right from the thumbnail.

[@omikronweapon]

How can you have a crush on someone simply by looks, implying attraction, and it being *platonic*?. It's almost the exact opposite of platonic. Your statement is indeed false. Now I'm wondering if you actually ONLY comment falsehoods.

[@camilohiche4475]

@@omikronweapon Thank you for making me check this comment so I come back to this video and admire this beautiful professor once again.

[@TymexComputing]

You omitted the pentagram, the goat and the blood :)

[@Triantalex]

false.

[@AnastasisGrammenos]

A cool application of this is in chemical storage units. There you have chemicals that shouldn't be close with some (conflict) and chemicals that are ok to be side by side (not conflict). So you need to get a storage unit with the min_vertex_ cover + 1 different rooms

[@pants1337]

Runescape's 'Recruitment Drive' quest.

[@ab12345cdf]

always think about this when i see this proble lol

[@Devan...]

first think i thought of. lol

[@andyrhodes1554]

I wish I had seen this video years ago when I did this quest...

[@arejm7304]

hahahhah awesome

[@jwrm22]

In the meantime, the wolf ate the cabbage as he was very hungry.

[@gorillaau]

jwrm22 The wolf relieved itself on the cabbage.... and smirked "Enjoy your dinner now"

[@johnbouttell5827]

After spending so much time in the boat, the wolf will soon become domesticated. He may end up rowing the boat. Wolf Boat Tours R' Us.

[@rockinRrr]

the wolf is the boat.

[@BeeryGamer]

Then we won't need the rower/owner of all those vegetables and animals no more, so the number of seats of the boat required will always be the lowest vertex number! Give me those millions now thank you very much!

[@RWBHere]

If the farmer rowed badly enough, and the river was rough, then the wolf would soon become too travel sick to eat anything.

[@jans1982]

Or maybe ff you do every trip with your wolf, then you'll be friends with the wolf and then leave him with his food on purpose

[@elimalinsky7069]

John Bicycle So that's how the wolf became a dog? Being ferried from one bank of the river to the other :D

[@vimalk78]

This is perhaps my favorite numberphile video.

[@ROL4NDpkmnguide]

I like her accent

[@paint4pain]

French Canadian, probably from greater Montreal area.

[@monkey7431_]

Sounds Dutch to me mate

[@joewhitmore6776]

I was just wondering what kind of accent is that

[@timhoheisel8939]

French-Canadian, in fact, Montreal.

[@alvkarthik2018]

i have heard this problem a hundred times but never thought that people are actually serious about these kind of problems. and that;s why i love numberphile .

[@shahbazsheikh3545]

"Blood everywhere or shreds of cabbage".... hahahaha! Great video.

[@rohansastry]

Shahbaz Sheikh Sheds of broccoli everywhere

[@MrTheNaboo]

Graph theory seems to pop up everywhere.

[@anselmschueler]

Maximilian Wollner it does

[@kailomonkey]

Because graph theory says this problem can get too complicated let's just draw it as a network, try our best then declare it too complicated.

[@mensaswede4028]

Yeah, graphs are succinct representation of “things” (vertices) and “relationships between things” (edges). And a lot of problems deal with things and the relationships between those things.

[@Dominikcos7]

*insert the cabbage scene from avatar here*

[@serkanmuhcu1270]

My cabbages!

[@fossilfighters101]

mY cAbBaGeS

[@Greg042869]

I don't remember, did that look like broccoli?

[@sweatygenius]

I loved this

[@LaGuerre19]

My broccoli brings all the goats to the yard

[@acbonbe7059]

LaGuerre19 no that’s a carrot

[@mihaitmf]

Really cool stuff behind an apparently easy problem. Plus, I love how mathematicians write so neatly on thoes big paper sheets.

[@olliestone5549]

They should invite Big Shaq here... His math skills are mind boggling.

[@OEpistimon]

The mathematicians working with numberphile wouldn't be able to comprehend his quick mafs...

[@philipsneck3571]

Agreed, his mafs are just too dang quick

[@neelparmar6690]

Mathememagics ting

[@cosmicjenny4508]

+Purposely Mistaken Nah, man was decent at maffs. Man got... D...

[@alandouglas2789]

Purposely Mistaken lol, seriously?

[@franktoffel]

Excellent explanation! I really like the way it drives you to the limitation of the initial thought. More of these!!

[@rohansastry]

But... goats eat everything! So... wouldn’t the goat also eat the boat?

[@lukasschmidt2478]

For the puzzle to work though, none of the animals must do anything when the farmer is watching.

[@josephoduor2358]

Says the one who has a wolf as a pet

[@pleasedontwatchthese9593]

The 🐐 ate the 🚜.

[@pmcpartlan]

Rohan Sastry If a goat ate a boat, would it float?

[@Nemelis0]

@Pete McPartlan: Only in a moat

[@flinkwieeinwiesel5657]

Wow, what an inspiring and cheerful way to present the problem. More please!

[@mikewilliams6025]

Wolf would definitely eat the cat. You've broken math, Brady. Stop that.

[@StezzerLolz]

The cat would eat the rabbit, too. And the goose would just destroy everything in a psychotic rampage, because geese are bastards.

[@gabehennessy-oreilly1177]

Nice callback

[@Siggvard]

The cat could climb up a tree.

[@Siggvard]

The cat could climb up a tree.

[@HappyBeezerStudios]

The cat would climb up the boat.

[@iamalexkempton]

This is some classic numberphile right here!

[@dragoncurveenthusiast]

As a kid I always wondered how the farmer keeps the wolf from eating the goat and the goat from eating the cabbage if he IS there with them. I never got an answer.

[@lucianodebenedictis6014]

He just says: "No, you can't".

[@gabehennessy-oreilly1177]

He makes them attempt to prove the collatz conjecture

[@liltonyabc]

Swiper no swiping

[@Gold161803]

Spray bottle?

[@NathanK97]

he has an oar and not a flimsy plastic one... a solid hand carved oak oar

[@MateusSFigueiredo]

She's great! Do more videos with her

[@brenthooton3412]

14:15 the interesting question is the balance between efficiency (do it in as few crossings as possible) vs capacity (get away with the smallest boat as possible). 7 crossings for 5 animals seems really inefficient. But maybe the cost of a bigger boat outweighs the cost of the extra crossings. Or maybe the river is really wide and the cost of the extra crossings makes the bigger boat worth it.

[@housellama]

Found the engineer!

[@kennethgee2004]

@@housellama well probably, but optimization issue are also in mathematics with the equilibrium theory discovered by Nash. The optimization issue has also been extended into law and other areas, so it is an important concept.

[@ninogaggi]

Why would a farmer have a wolf?

[@wierdalien1]

Alan Murray 4000bc farmer

[@numberphile]

kzbin.info/www/bejne/enXdhayFf7iYY7s

[@ritikchawla8298]

lol

[@ninogaggi]

Numberphile yes that was my inspiration

[@revjmyoung]

Thank you for this -- I had the same thought from Gareth! ;-)

[@jukka-pekkatuominen4540]

The Wolf would definitely eat the Cat.

[@SuperSMT]

And the cat would eat the rabbit... My cat has

[@MateusSFigueiredo]

it would have to get the cat first

[@jukka-pekkatuominen4540]

If the Cat runs away you'll end up losing them both. So in case of riddle it wouldn't work either.

[@cyberneticube]

And the goose would definitely eat the carrot and the cabbage, but what does it really matter, it's just en example :)

[@seraphimwiththecheese5880]

Cats eat grass. I've seen mine do it.

[@sachamm]

Great stuff, I love how your subjects are so enthusiastic. We definitely need more on complexity theory!

[@beeeesac]

Always loved problems like these!

[@neelparmar6690]

Many years of playing Professor Layton have prepared me for unexpected river crossings...I'm sure it will happen one of these days...

[@bidaubadeadieu]

Really nice video, one of my favorites from recent Numberphile. I love the introduction of a simple problem followed by the general case, much like the Josephus video.

[@CharlesTheClumsy]

I don't know any other channel that puts their name in the title of every video.

[@azbyn692]

Computerphile also does it

[@frozenglobe]

and Sixty Symbols

[@JohnDCrafton]

It's for search engine optimization (SEO).

[@subinmdr]

Smarter Every Day and almost every singer and band channels

[@cyrillamat4888]

I do

[@hossamel2006]

Somehow this is an amazing video...probably the best one I've ever watched 😃

[@delve_]

Roses are red Violets are fine You see this here hyphen ~ It's a Parker Line

[@kye4840]

~~~~~Tilde not hyphen~~~~~

[@delve_]

+Ky E [thatstheidea]

[@thexavier666]

That's a Parker Square of a poem

[@Triantalex]

false.

[@macacoman]

One of my favorite videos! Great job you guys.

[@AgentM124]

P=NP? N=1 then. QED

[@meh6422]

Wow ya so smart, very intellectual much IQ

[@AgentM124]

Horus yas yas. I used to watch Rick and Morty! 🙃

[@scottgoodson8295]

Agent M Or P=0

[@astamite-]

This is almost 100% correct. The only thing missing is that you forgot to prove P=NP.

[@AgentM124]

Astamite true, also wasn't P the variable, so setting it to 0 would mean N could be anything. But meh, I won't ever become a farmer so I don't bother.

[@anteconfig5391]

You just gave me an easy problem to see if p = np thanks. Now I know which puzzle to do when I get bored.

[@yero]

I think I fell in love ❤ also I think that the wolf would eat the cat if it was really hungry

[@jiggely_spears]

A wolf is basically a dog - it would eat ALL the things...

[@theendofit]

Pffft....sence when can cabages not swim.

[@SolitaryCZ]

theendofit It's common knowledge. No vegetable can swim... the wheelchair is too heavy.

[@Superphilipp]

SolitaryCZ, I lol'ed

[@SUPAAH_]

how heavy is the cabbage that you cannot hold it?

[@stapler942]

A cabbage would sink in water, otherwise it would be a witch.

[@ajtheown]

As a Tim, I appreciate your use of emojis from a variety of platforms :)

[@ProgresistTaliban]

But...Why she has a Wolf in the first place?

[@Derpster2493]

Mittens.

[@Gumshoesamurai]

Protection from other wolves. Camouflage? An "apex predator" makes your party a danger to aggress (attack).

[@jakubpekarek6400]

So the wolf doesn't attack goats the farmer has at home. Remember? You need to take the troublemaker with you everywhere, every time. Duh.

[@LinkEX]

I guess that's one reason why mathematicians are sometimes perceived as aloof, living in surreal imaginary world; and why exploring math is actually far more creative and far from dry and formulaic, as some would argue.

[@OriginalPiMan]

Guard dog.

[@mraBJJ33]

I'm not smart enough to know the practical application of this but it was still really cool to learn about it in a way that was easy for me to follow along.

[@ndavid42]

"the rabbit and the goat together are fine. there won't be *too much* violence there" TOO MUCH??!

[@mikeybud3501]

Very interesting mathematical take on this ancient riddle. Love it as always! 😛

[@althaz]

Well I *was* going to go to bed, Brady, but I guess I'll watch this first instead :).

[@EdithKFrost]

Cats are so badass that even the wolf is too afraid to eat them.

[@SmileyMPV]

But finding the minimum vertex cover was NP hard already :p

[@johnredberg]

In all fairness: Given the classical result that the minimum vertex cover problem is NP-hard, it is not surprising that the "do I need an extra seat" problem is at least NP-hard as well.

[@isaacbankart]

0:45 i'm glad the cabbage can't swim that would be really worrying

[@Mrqwerty2109]

Learned about this problem from Professor Layton

[@riccardopratesi7943]

What about the case of one character being at risk of suicide, and it cannot be left alone? or it can be left only with some of the others? I mean, if in the graph there are also lines linking oneself, but only in absence of some other vertex?

[@moorentje]

At the end you see a penguin and a bee emoji fade in. A cheeky nod for us Tims :)

[@将軍九八.彁]

wolf can't eat the cat, lol

[@piotrarturklos]

The cat would be way too annoying as prey, scratching the eyes and running between the legs.

[@soberhippie]

Given half a chance, a cat might eat the wolf.

[@RWBHere]

Or run up a tree.

[@ChrisWalshZX]

9 things to take across. There are 2^9 = 512 potential vertex covers (brute force) to check. There will be plenty of ways to eliminate this combos though. As we're looking for the minimum vertex cover, we can start with 9 x 1 VC, then 2 VC, then 3VC etc.

[@JohnDCrafton]

A wolf will definitely eat a cat, if it can catch the cat.

[@JohnDCrafton]

So? I have personally seen a mild-mannered dog rip a cat to shreds (the dog just wanted to play, but unfortunately for the cat, he played too rough). Wolves are decidedly less mild-mannered than dogs.

[@hart-of-gold]

When I was a kid our cat (a small tom cat) beat a large rottweiler by climbing on to the back of its neck and clawing the eyes and chewing its ears.

[@JohnDCrafton]

We can exchange anecdotes until we die, doesn't change the fact that a wolf will at least try to eat a cat, and will have varying levels of success depending on the intelligence and fitness of the cat. But if the cat gets away it's most likely gone up a tree, and then the farmer has a different problem on his hands.

[@PuzzleQodec]

At least the wolf and cat will be sufficiently distracted from eating anything else, so the farmer can bring the rest of his stuff to the other side of the river, and his boat can be smaller.

[@JB-kn2zh]

Obviously we have a much more sophisticated knowledge of this problem now than when Alcuin wrote it down, but I'm still impressed by the puzzles and ideas medieval thinkers came up with.

[@menturinai1387]

What is the smallest number of trips required?

[@darkfire8008]

7

[@doodelay]

I'm convinced that math problems are more fun then physics problems because they can be as playful as the one who imagined them but the generalizations are so profound

[@ethanpfeiffer7403]

I prefer the Professor Layton river crossings.

[@neelparmar6690]

One of these days solving all of those Layton puzzles will come in handy in real life...one day soon I'm sure...

[@adriansarbu2001]

I think that if the vertex cover is equal or bigger than the remaining vertices (after removing the vertex cover) divided by two then you will need a boat with the minimum places else you will need a boat with minimum places plus one (sorry for bad english)

[@swaiii]

This is some anti wolf propaganda. From my point of view the cabbage is the evil one

[@pavphone2616]

Well then you are lost!

[@omikronweapon]

how about that sadistic farmer that keeps messing with everybody.

[@purplewine7362]

only a wolf deals in absolutes

[@loneboatmapping4298]

It's actually easy to prove, because the network that would form in any of the 2 sides is a simplified version of the bigger net (With fewer conections) so it will require the same, if not less, cover

[@CaptainHandsome]

Why does the Farmer have a wolf?

[@EnginAtik]

Conjecture: Define a measure for the nodes to belong to a vertex cover as: number of loops they are part of plus number edges they have. Remove the node that has the highest measure from the graph by zeroing the row and column that belongs to this node in the incidence matrix. Repeat the process until the rank of the incidence matrix is zero. This will give the minimum vertex cover. Measure = diag(a*a) + a*ones(nodecount,1), where a is the incidence matrix.

[@EnginAtik]

Also going to the other side of the river and and coming back is the same thing. It is symmetric: if you film the successful boat crossing and watch it backwards we will note that nobody eats anybody this time either. This symmetry could be useful in figuring out whether boat size should be one more than the minimum vertex cover.

[@bongjoobrianlee]

Cabbage looks like a Broccoli

[@ragnkja]

Bong Joo Brian Lee Whatever, it’s the same species.

[@ivarkrabol]

Thought of a quick method to check that a vertex cover is minimal in some cases: the vertex cover must be minimal if you can find a matching which matches all its vertices, i.e. a set of edges which do not share any vertices and which "touches" each of the vertex cover's vertices. This because 1) the minimum vertex cover (mvc) of a graph must necessarily be at least as big as the mvc of any subgraph; 2) the size of the mvc of a graph formed from the edges of a matching and their vertices would necessarily be equal to the number of edges in the matching. Might be useless and/or obvious, but I though it worth mentioning, since "it's actually not such an easy thing to check."

[@rollstuhlmeister]

What if the wolf eats the farmer???

[@yingo4098]

I like how the 'cabbage', the carrot and the grass can get on and off the boat by itself

[@Luxalpa]

The cat would definitely eat the rabbit and it would probably try the goose too.

[@KenGray]

Fascinating Topic in general. I always like watching your stuff because I learn something new every time, if I can make it through. Also I find fascinating in the US, we call that broccoli not cabbage.

[@saras8166]

I've not seen a single comment about the problem itself yet.

[@yvesivo]

Sara S Me neither. I hoped for some comments on the P NP topic

[@andrewl5267]

Then you haven't seen mine yet ( ͡° ͜ʖ ͡°)

[@JesseGilbride]

More Dr. Annie Raymond videos, please.

[@laptop006]

Rabbit's can't cut through steel beams

[@ragnkja]

LapTop006 [citation needed]

[@stevethecatcouch6532]

A farmer is trying to cross a river with a wolf, a rabbit, and a steel beam ...

[@jiggely_spears]

Neither can burning aviation fuel....

[@mensaswede4028]

I love how there is always a line in these videos where the guest says “I’ll need another piece of paper...”

[@pizzamannetje79]

What does "NP hard" mean?

[@IDoNotLikeHandlesOnYT]

(I could easily be wrong, but here it is as I understand it.) In basic terms, as it applies here, there's no way to solve the problem analytically; you have to use trial and error. More advanced explanation: en.wikipedia.org/wiki/P_versus_NP_problem

[@antanis]

Look up p vs np and the computational zoo by hackerdashery.

[@mothman.industries]

Geese having Teeths is the most terrifying thing I'll ever learn from this channel, tbh.

[@dbsirius]

VIP cabbage

[@tohopes]

*RIP cabbage

[@neelparmar6690]

But it was a broccoli in the visuals...

[@mikerich32]

Neel Parmar Broccoli is a type of cabbage, so *technically* the visual wasn't wrong lol

[@tohopes]

Broccoli is not a type of cabbage. They're different varieties of the same species. Stop.

[@antman7673]

AERO BLKHWK32 surely broccoli is made of many small leaves of cabbage.

[@ColemanMulkerin]

Such a simple problem but I have seen like 3 interesting videos on KZbin approaching and expanding on this problem from different angles.

[@danieltaber4924]

That's not a cabbage. That's a Broccoli.

[@Aoltooliol]

Daniel Taber same species

[@RWBHere]

One word for that: Brassica!

[@TigruArdavi]

@@RWBHere Wrong, two words for this: _Brassica oleracea_

[@salehinkibria8377]

the distinction between minimum vertex cover and minimum vertex cover + 1 cases seems simple enough. We must simply determine if any part of the minimum vertex cover is connected to more than one vertex outside the minimum cover. if so, it is a minimum vertex cover + 1 case, else minimum vertex cover case.

[@2supertux]

what if the wolf decide to not eat the mouse ? like chewbacca with the porg

[@CesarDainezi]

"If you were able come up with a polynomial time algorithm to determine it for any graph what it is, then you would prove that P = NP." That plot twist!

[@beeble2003]

Not much of a plot twist, really. It's extremely common for problems in graph theory to be NP-hard. Once you've seen a hundred of them, the only reason this one is interesting is because the problem is "Is the answer x or x+1?" Another similar one is that, but the four-colour theorem, every planar graph can be coloured with four colours, but it turns out to be NP-complete to determine whether a planar graph is 3-colourable.

[@heraok1766]

Please publish a video which the word mathemathics pronounced by everyone who prepared a numberphile video 🙄

[@rohansastry]

MatheMATHics?!?!?

[@mathaha2922]

I see David Eisenbud in a window near the end. How about a video of him and his recollections of Paul Halmos?

[@SlideRulePirate]

This vid is blatantly Vegist. The Wolf gets a sound effect as does the Goat, but the Cabbages don't. End the shaming. Justice for Cabbages!!!

[@JohnDCrafton]

What sound does a cabbage make? (and why does the cabbage look like broccoli?)

[@ragnkja]

SlideRulePirate I think the word might be “kingdom-ist” since it discriminates between kingdom Plantae and kingdom Animalia. 😉

[@Uninactive]

*Cabbage noises*

[@SlideRulePirate]

We're never going to make progress if all anyone ever does is try to make sense.

[@Dorian_sapiens]

The cries of the carrots!

[@calebmarston4729]

At first I thought the plus one or not would be easy. You just determine whether the items not in the vertex cover were twice or more of the items in the vertex cover. But then I realized that not every item in the vertex cover conflicts with every item outside it

[@mikejohnstonbob935]

tis like a graph coloring problem