3
$\begingroup$

Let $G$ be a disconnected graph. Prove that its complement $\bar{G}$ is connected.

I would like to check if my proof of the above (rather famous) problem is valid. It is as follows:

Since $G$ is disconnected, its vertex set can be partitioned into $2$ disjoint vertex sets, $V_1$ and $V_2,$ such that each vertex is only adjacent to vertices in the same set as it. Hence, in $\bar{G}$, each vertex is adjacent to all the vertices in the other set, and will not be adjacent to any vertex in the same set as it. in other words, $\bar{G}$ is a complete bipartite graph, which is clearly connected, so we are done.

$\endgroup$

2 Answers 2

3
$\begingroup$

This is not correct. It is in general not true that each vertex in $V_1$ will be adjacent to all other vertices in $V_1$. That would only be the case with graphs that are a union of several complete graphs.
So the complementary graph is certainly not always a complete bipartite graph, it could have more edges as well. But the important thing here is that this complete bipartite graphs is always a subgraph of $\bar{G}$ containing all vertices of $\bar{G}$. Therefore it is indeed connected.

$\endgroup$
2
$\begingroup$

This answer may be too late, but you can't assume there are only 2 disjoint vertex sets, and you also can't assume that the vertices in some $V_i$ are adjacent to one another. You're on the right track, however, because we do want to partition V into disjoint sets. I've included a formal proof that uses this approach.

Edit: As @JaapScherphuis pointed out, I was wrong in assuming we need to define more than two sets since we need only prove the graph is connected. So another (less complicated) approach to the proof is to instead consider the vertex set $V_1$ of some component in $G$ and the set $V \setminus V_1$ to complete the proof.

Proof:

Let $G = (V,E)$ be a disconnected graph and let $\overline{G}$ be the complement of $G$. Define $\sim$ as an equivalence relation such that for any $x,y \in V(G), x \sim y$ iff there exists a walk between x and y in $G$. Since $G$ is disconnected, then $\coprod_{i = 1}^{n} V_i$ is a partition of $V$ into classes of the relation $\sim$ and $n > 1$. Let $z_i, z_j \in V$, and let $\{ z_i, z_j \} \in \binom{V}{2} \setminus E$ (i.e. let $z_i, z_j$ be arbitrary vertices such that they do not share an edge in $G$). Since $\binom{V}{2} \setminus E$ is the edge set of $\overline{G}$, $z_i \sim z_j$ in $\overline{G}$. If $\coprod_{i = 1}^{n} V_i = \emptyset$, $\overline{G}$ is connected since $\{ z_i, z_j \} \in \binom{V}{2} \setminus E$. Otherwise, we consider $v_i, u_i \in V_i$, which means $ \{ v_i, u_i \} \notin \binom{V}{2} \setminus E$ (i.e. $v_i$ and $u_i$ are in the same component and share an edge in $G$ but do not share an edge in $\overline{G}$). Additionally, let $v_j \in V_j$ where $j \neq i$(i.e. in a different component). Then, a walk between $v_i$ and $u_i$ is formed with the edges $\{ u_i, v_j \}$ and $\{ u_i, v_i \}$ (since $\sim$ is an equivalence relation and therefore transitive). Thus, a path exists between all $v_i, v_j \in V$.

$\endgroup$
5
  • 2
    $\begingroup$ If the graph has more than two connected components, then you can still split the vertices into two disjoint vertex sets. You don't have to split it into as many sets as possible, just because you can. Using just two sets keeps the proof simpler. There is no requirement that each set forms a single connected component, just that the two sets are not connected to each other. $\endgroup$ Aug 23, 2022 at 9:39
  • $\begingroup$ @JaapScherphuis could you elaborate on how you would define these sets because, at least in the manner I've defined them, each vertex set must correspond to a single component in order for the sets to be disjoint, implying that more than 2 components requires more than 2 vertex sets. $\endgroup$ Aug 23, 2022 at 10:20
  • 2
    $\begingroup$ Pick one of the connected components of the graph. Let $V_1$ be the vertices of that component, and let $V_2=V-V_1$ be the set of all the vertices not in $V_1$. As explained in the other answer, the complement of G has $K(V_1,V_2)$ as a subgraph, which is a connected graph on $V$. $\endgroup$ Aug 23, 2022 at 10:22
  • $\begingroup$ @JaapScherphuis I see it now. Thank you. I lost track of the fact that we're proving the graph is connected, not necessarily how it is connected. I'll make a comment on this in the original post. $\endgroup$ Aug 23, 2022 at 10:26
  • 1
    $\begingroup$ Your proof is fine though, it just read as if it implied that the other answer was wrong. $\endgroup$ Aug 23, 2022 at 10:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .