Complement of Vertex Cover is Independent Vertex Set | Graph Theory
Вставка
- Опубліковано 25 сер 2024
- We prove the complement of a vertex cover is an independent vertex set. Recall a vertex cover is a set of vertices covering all edges of the graph, meaning every edge has at least one end vertex in the cover. As a result, the complement of a cover cannot possible have two vertices joined by an edge, and so it will be an independent set as we prove in this lesson using a proof by contradiction. This gives us some intuition for the fact that a covering number plus an independence number is the order of the graph. #GraphTheory
Independent Vertex Sets: • Independent Vertex Set...
Vertex Covers: • Vertex Covers and Vert...
Proof Covering Number plus Independence Number is Order of Graph: coming soon
★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
I should have mentioned the converse is true as well. Of course, the complement of a complement is the original set. So if we take the complement of a vertex cover, we get an independent set, and if we take the complement of that we get back to the cover. However this doesn't mean that EVERY independent set has a cover as a complement. But it is true, as you can prove using a very similar strategy to what we did in this lesson. Just know the proof we did in this lesson, together with the properties of a complement, DOES NOT imply the converse is true. We'll prove the converse soon, and check out my lesson on vertex covers if you need to! ua-cam.com/video/1KkT7y8nxH0/v-deo.html
ok.
hmmmmmmm....
I have my final exam on the 22nd of Aug, after a week, and I've been looking for some explanation videos of these concepts and found your channel yesterday and this now this, it's like you're sitting 10000 km away from me and teaching me personally, coz this is the exact thing I was searching for. Beautiful. Thank you !!
Which country do you live in?
Complement? More like "Cool videos that are heaven-sent!" 👍
Wrath of Math does a fine job of covering graph theory! 😃
Haha, thank you Ezra! I do my best, we're well on the way to 200 videos in the graph theory playlist!
GREAT JOB BRILLIANT EXPLANATION!
Thank you!
@@WrathofMath you welcome!