filmov
tv
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.
********************************************************************
+WRATH OF MATH+
Follow Wrath of Math on...
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.
********************************************************************
+WRATH OF MATH+
Follow Wrath of Math on...
0:06:44
Proof: A Graph or its Complement Must be Connected | Graph Theory, Graph Complements
0:09:53
Proof: A Graph or its Complement is not Bipartite | Graph Theory, Bipartite Graphs
0:06:58
Proof: Bipartite Graphs have no Odd Cycles | Graph Theory, Bipartite Theorem, Proofs
0:20:05
Proof: If a Graph has no Odd Cycles then it is Bipartite | Graph Theory, Bipartite Theorem
0:06:52
Proof: Every Graph has an Even Number of Odd Degree Vertices | Graph Theory
0:19:23
Proof: Graph is Eulerian iff All Vertices have Even Degree | Euler Circuits, Graph Theory
0:10:39
Weak Perfect Graph Theorem
0:05:58
Proof: Graph with all Even Degree Vertices has no Bridges | Graph Theory
2:07:02
A New Approach to Strong Convergence - Ramon Van Handel
0:08:43
Proof: Connected Graph of Order n Has at least n-1 Edges | Graph Theory
0:09:20
Proof: Graph is a Tree iff Unique Paths for Each Vertex Pair | Graph Theory, Tree Graphs
0:09:53
Proof: Graph has a Cycle Longer than its Minimum Degree | Graph Theory
0:12:45
Which Sequences are Graphical? (Degree Sequences and Havel-Hakimi algorithm) | Graph Theory
0:07:26
Proof: Minimum Degree Condition for Connected Graphs | Graph Theory
0:03:32
Graph Theory: 06 Sum of Degrees is ALWAYS Twice the Number of Edges
0:16:05
Proof: Dirac's Theorem for Hamiltonian Graphs | Hamiltonian Cycles, Graph Theory
0:15:55
Proof: Euler's Formula for Plane Graphs | Graph Theory
0:14:36
Proof: Ore's Theorem for Hamiltonian Graphs | Sufficient Condition for Hamilton Graphs, Graph T...
0:33:23
INTRODUCTION to GRAPH THEORY - DISCRETE MATHEMATICS
0:09:41
MAC 281: Graph Theory Proof by (Strong) Induction
0:03:53
Complement of a disconnected graph is connected Solution
0:11:44
Proof: Graph with n Vertices and n-1 Edges is a Tree | Graph Theory
0:07:48
Simple graph and its theorem
0:05:22
Proof: Every Graph Contains Minimum Degree Length Path | Graph Theory
Комментарии