Complement of Independent Set is Vertex Cover | Graph Theory

We prove the complement of an independent vertex set is a vertex cover. This makes for an easy direct proof once we recall our definitions. An independent vertex set is a set of vertices, no two of which are adjacent. A vertex cover is a set of vertices such that every edge has at least one end vertex in the cover. The vertex cover is said to cover the graph, or cover all edges of the graph. Then, if we take an arbitrary independent set X from a graph G, and take an edge uv from G, we know u is not in X or v is not in X. This is because if they were both in the independent set X - that would contradict X having no adjacent vertices. Thus, u is in X complement or v is in X complement. We see every edge has at least one end vertex in the complement of our independent set, and so the complement is a vertex cover. #GraphTheory
Independent Vertex Sets: • Independent Vertex Set...
Vertex Covers: • Vertex Covers and Vert...
Complement of Vertex Cover is Independent Set: • Complement of Vertex C...
Graph Theory playlist: • Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/...
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.ba...
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050

[@WrathofMath]

Check out my lesson introducing vertex covers: ua-cam.com/video/1KkT7y8nxH0/v-deo.html
Or check out the proof that the complement of a vertex cover is an independent set: ua-cam.com/video/Sl85juLEHBE/v-deo.html

[@punditgi]

You cover covers quite well, sir!
😃

[@WrathofMath]

Thanks, Ezra! I'll keep covering covers until I've uncovered all there is to cover about covers!

[@punditgi]

@@WrathofMath Copy that. 😃

[@PunmasterSTP]

Seems like you got all the puns covered 👍

[@g.y2338]

I hear sheldon cooper speaking when I close my eyes

[@WrathofMath]

I seem to get that a lot. Thanks for watching and check out my graph theory playlist for more! ua-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html

[@PunmasterSTP]

Complement of independent set? More like "Cool videos, and they are super useful; we're all set!"

[@shadabdulsamad9205]

Thanks
But could you explain spanning trees please?

[@aashsyed1277]

thanks a lot!

[@aashsyed1277]

hey! do you use a screen recorder?
notability can't write with your hand until you don't make that mode on.

[@LearningCS-jp4cb]

you can see in notification bar, screen recorder is on.

[@tannercypret3171]

Request: Reduce Independent Set to Clique.

[@exSnake]

Could C be a vertex cover?

[@Mayoninja]

Big tuff math.

[@WrathofMath]

That's all we offer here

[@aashsyed1277]

@@WrathofMath how did he time travel?