Please fill in the below blanks If a graph G is NOT connected, then the compleme
ID: 2971049 • Letter: P
Question
Please fill in the below blanks
If a graph G is NOT connected, then the complement of the graph, Gc, MUST be connected. proof: We will show the statement is true if G has 2 distinct components C and D. (Our proof could then be generalized for graphs with more than one component.) Let u and v be any two vertices in Gc We must show that there is a path in Gc that connects u and v. All vertices in Gc are also vertices in G. Consider these two possibilities. Suppose u and v are not in the same component of G. Without loss of generality, suppose u is in C and v is in D. Since C and D are distinct components, they are not connected to each other. Therefore, the edge , is not in G. Hence, u,v is an edge in graph and we have a path connecting the two vertices in Gc. Now, suppose u and v lie in the same component of G. (Say u and v are in C.) Since D is a component of G, D is nonempty. There must be some vertex w in D. Label those three vertices in the illustration below. Now, since vertices and are not in the same component of G, is not in the graph Therefore, the edges and are in the graph . Hence, the path , lies in GC. Here is an illustration. Label the vertices as before and draw any included edges. Thus, since any two vertices in Gc are connected by a path in Gc, we know Gc is a connected graph.Explanation / Answer
Please fill in the below blanks If a graph G is NOT connected, then the compleme