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

★DONATE★

Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!

Follow Wrath of Math on...

[PunmasterSTP]

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

[g.y]

I hear sheldon cooper speaking when I close my eyes

[aashsyed]

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

[shadabdulsamad]

Thanks
But could you explain spanning trees please?

[tannercypret]

Request: Reduce Independent Set to Clique.