Proof: A Graph or its Complement Must be Connected | Graph Theory, Graph Complements

A graph and its complement cannot both be disconnected. Why is this? We'll find out in today's video graph theory lesson, where we prove that at least one of a graph or its complement has to be connected!

The proof is fairly straightforward, we begin with a disconnected graph G and want to show that its complement must be connected. We take two distinct vertices in G, and if we can show these arbitrary distinct vertices must be adjacent in G complement, then we will have shown G complement is connected. This is because G and G complement have the same vertex set by definition of graph complement, so we only have to consider vertices of G!

We first suppose our two vertices are in different components of G, thus they are not adjacent in G and therefore must be adjacent in G complement, so they are connected.

Then we suppose our two vertices u and v are in the same component of G. Then there is some other vertex w in a different component that is not adjacent to u and is not adjacent to v (since u and v are in a different component from w). Thus, u and w aren't adjacent in G and v and w aren't adjacent in G. Hence, uw is an edge of G complement as is vw. Therefore (u, w, v) is a u-v path in G complement so u and v are connected.

And that is all!



I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp:
Vallow Spotify:
Vallow SoundCloud:
********************************************************************

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:

Follow Wrath of Math on...
● Instagram:
● Facebook:
● Twitter:

My Music Channel:

wrath of math,math lessons,math,education,math video,graph theory,graph theory proof,complement graph,disonnected complement graph,complement graph proof,connectivity proof,