Vertex Covers and Vertex Covering Numbers | Graph Theory

We introduce vertex covers, minimum vertex covers, and vertex covering numbers! We'll see some examples and non-examples of vertex covers, as well as minimum vertex covers and some that aren't minimum. The number of vertices in a minimum vertex cover is called the vertex covering number of the graph. We'll discuss why the complement of a vertex cover is an independent vertex set, and see how the covering number plus the independence number is the order of a graph (Gallai identity). We'll also discuss covering numbers of complete graphs, cycles, and complete bipartite graphs. #GraphTheory

A vertex is said to cover its incident edges. A set of vertices is a vertex cover is if covers every edge in the graph.

Independent Vertex Sets:    • Independent Vertex Sets and Independe...  
Proof Complement of Vertex Cover is Independent Set:    • Complement of Vertex Cover is Indepen...  
Proof Covering Number plus Independence Number is Order of Graph: (coming soon)

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: https://www.paypal.me/wrathofmath

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: https://crayonangel.bandcamp.com/

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

My Music Channel:    / @emery3050