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

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out my math fashion brand! https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

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.

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

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