The complement of a graph G
I have a homework problem where I have a graph $G$ and I am tasked with proving that at least one of $G$ and $G$ complement is connected. However, I am unclear on the exact meaning of $G$ complement.
For example, let's imagine I have a disconnected graph with four vertices $(V_1, V_2, V_3, \text{and } V_4)$. If the edges form a sort of box where the bottom edge is left disconnected, would $G$ complement have that edge filled in along with the cross edges as well? Furthermore, does $G$ complement contain all of the edges in $G$ or just the edges not contained in $G$? Thanks for taking the time to read.
$\endgroup$3 Answers
$\begingroup$Complement means the graph with same vertices and the missing edges.
Hint for the problem If $G$ is connected you are done. If $G$ is disconnected, let $u, v$ be vertices in two different components of $G$.
Then $uv$ is an edge in the complement of $G$. Moreover, if $w$ is any other vertex in $G$, then at least one of $uw, vw$ has to be an edge in the complement. This way you can coonect $w$ to both $u$ and $v$ in the complement, and from here you can prove that the complement is connected.
$\endgroup$ 3 $\begingroup$$G$ complement has exactly the edges not contained in $G$, and $G$ complement has the same vertices as $G$.
$\endgroup$ 2 $\begingroup$Given a graph $G=(V,E)$, its complement graph is precisely the graph $(V,V^{(2)}-E)$, where $V^{(2)}$ consists of all 2-subsets of $V$. Thus, the complement graph has the same vertex set as $G$, and its edge set consists exactly of all edges of the complete graph $K_n$ that are not in $G$, where $n=|V|$ is the number of vertices of $G$.
Thus, the complement graph of $G=(V,E)$ consists of exactly $\binom{n}{2} - |E|$ edges, and the total number of edges in $G$ and in its complement will add up to exactly the number of edges of the complete graph $K_n$, i.e. to $\binom{n}{2}$.
To prove that at least one of $G$ or its complement $\overline{G}$ is connected, suppose $G$ is not connected and has connected components $G_1,G_2,\ldots$. Then in the complement graph every vertex of $G_i$ is connected to every vertex of $G_j$, whenever $i \ne j$. Thus, $\overline{G}$ is connected.
$\endgroup$
