I was tasked to prove that when given 2 graphs $G$ and $\bar{G}$ (complement), at least one of them is a always a connected graph.
Well, I always post my attempt at solution, but here I'm totally stuck. I tried to do raw algebraic manipulations with # of components, circuit ranks, etc, but to no avail. So I really hope someone could give me a hint on how to approach this problem.
$\endgroup$ 09 Answers
$\begingroup$Suppose $G$ is disconnected. We want to show that $\bar{G}$ is connected. So suppose $v$ and $w$ are vertices. If $vw$ is not an edge in $G$, then it is an edge in $\bar{G}$, and so we have a path from $v$ to $w$ in $\bar{G}$. On the other hand, if $vw$ is an edge in $G$, then this means $v$ and $w$ are in the same component of $G$. Since $G$ is disconnected, we can find a vertex $u$ in a different component, so that neither $uv$ nor $uw$ are edges of $G$. Then $vuw$ is a parth from $v$ to $w$ in $\bar{G}$.
This shows that any two vertices in $\bar{G}$ have a path (in fact a path of length one or two) between them in $\bar{G}$, so $\bar{G}$ is connected.
$\endgroup$ 4 $\begingroup$If $\bar G$, the complement of $G$, is not connected, then there exists a partitioning of vertices into two disjoint sets $V_1$ and $V_2$ such that no edge of the complement is between them, i.e. for all $v_1 \in V_1$ and $v_2 \in V_2$ we have $\langle v_1,v_2\rangle \notin \bar E$. However, this means that for all $v_1$ and $v_2$ from $V_1$ and $V_2$ respectively, $\langle v_1,v_2 \rangle \in E$, hence $G$ is connected.
I hope this helps ;-)
$\endgroup$ 2 $\begingroup$I'm not very clever, and thinking gives me a headache. Let's try to solve this thing with a minimum of cleverness and hard thinking. A little brute force is OK.
Let's try for a proof by contradiction, that will always work if anything does. So we assume a disconnected graph $G$ with disconnected complement $\overline G.$
Then there are two vertices $a,b$ which can't be connected by a path in $G,$ and there are two vertices $c,d$ which can't be connected by a path in $\overline G.$
Let $H$ be the subgraph of $G$ induced by $\{a,b,c,d\},$ a graph with $2,3,$ or $4$ vertices depending on how $\{a,b\}$ and $\{c,d\}$ overlap. (Maybe I could eliminate one of those cases if I thought about it. Nuts to that.) If two vertices can't be connected by a path in the big graph, then they can't be connected by a path in the subgraph, right? So $H$ and $\overline H$ are still disconnected.
Great, that means I only have to check disconnected graphs with $2,3,$ or $4$ vertices. I can do that with brute force!
Allowing myself a tiny bit of cleverness to save work: If my disconnected graph $H$ has a disconnected complement, and if I can add edges to $H$ without making it connected, then the complement (which is losing edges) will still be disconnected! So I only have to test maximal disconnected graphs!! With just a little bit of thought, I see that a maximal disconnected graph is the disjoint union of two complete graphs. Up to $4$ vertices, the only graphs I have to check are:$$K_1\cup K_1,\ K_1\cup K_2,\ K_1\cup K_3,\ K_2\cup K_2.$$The complements of those graphs are$$K_{1,1},\ K_{1,2},\ K_{1,3},\ K_{2,2}.$$The complements are all connected! That does it!!
Wait a minute, that's looking suspiciously similar to the proofs in the other answers.
$\endgroup$ $\begingroup$Let $G$ be a simple disconnected graph
$\Longrightarrow\ \exists$ atleast $2$ vertices, say $u$ and $v$ such that there does not exist a path between $u$ and $v$.
$\Longrightarrow$ All vertices of $G$ are not adjacent to both $u$ and $v$ (Why?). $u$ and $v$ are obviously not adjacent.
$\Longrightarrow$ In $\bar{G}$ all the vertices are adjacent to either $u$ or $v$ or both and $u$ is adjacent to $v$.
$\Longrightarrow$ Take any two vertices in $\bar{G}$, say $a$ and $b$, we see that $a$ can be adjacent to either $u$ or $v$ or both. Same holds for $b$. Since, $u$ and $v$ are adjacent, there must exist a path through either $u$ or $v$ or both that connects $a$ and $b$.
$\Longrightarrow$ Hence, $\bar{G}$ is connected.
Same holds for $G$, if $\bar{G}$ is disconnected. Thus, at least one of $G$ and $\bar{G}$ must be connected.
$\endgroup$ $\begingroup$Additionally, it will be easy if simply look at the adjacency matrix of the graph.
More explanation: The adjacency matrix of a disconnected graph will be block diagonal. Then think about its complement, if two vertices were in different connected component in the original graph, then they are adjacent in the complement; if two vertices were in the same connected component in the orginal graph, then a $2$-path connects them.
$\endgroup$ 5 $\begingroup$Suppose one of G = (V,E) and G' = (V,E) is disconnected; say G with components G., . . . .,Gk, k > 1, w.l.o.g since G = G''. Any two vertices v∉Gi and w∉Gj will be connected in G' since (a) if i 6≠j then vw ∉ E, so vw 2 E'. (b) if i = j then there must be a third vertex u in another component such that vu ∉ E and wu ∉ E. In this case, v and w would be connected in G' through edges vu,wu ∉ E'. Since any pair of vertices in G' are connected, G' is connected.
$\endgroup$ $\begingroup$Suppose $G$ is not connected and has $r$ components, $C_1,C_2,\cdots,C_r$.
For $x\in C_i$ and $y\in C_j$, with $i\ne j$, since the edge $xy\not\in E(G)$, hence $xy\in E(G^c)$.
Let $n_i=|C_i|$. Then the above statement implies $K(n_1,n_2,\cdots,n_r)\subseteq G^c$, where $K(n_1,n_2,\cdots,n_r)$ is the complete $r$-partite graph. Now obviously $K(n_1,n_2,\cdots,n_r)$ is connected, which implies $G^c$ is connected.
$\endgroup$ $\begingroup$This can be done with induction.
- Show it is true for $n$ vertices
- And then prove it for $n+1$ vertices by considering $2$ cases:
- $V_{n+1}$ is none off $\{V_1,V_2,\ldots,V_n\}$
- $V_{n+1}$ is connected to some of ${V_1, V_2,\ldots, V_n}, it will never be connected to all because then the graph will be connected.
This is another answer, showing $\bar{G}$ is connected in $3$ cases by showing there exists an $\{a,b\}$ path in each case. Let $x,y$ be vertices in $G$. Let $H$ be the component that holds the vertex $x$ but not $y$.
C1: Suppose $a$ and $b$ are arbitrary vertices not in $H$. Then $x\sim a$ and $x\sim b$ in $\bar{G}$ so there is a unique $\{a,b\}$ path in $\bar{G}$, namely $\{a,x,b\}$. ($\sim$ means adjacent)
C2: Suppose $H$ holds one of the two vertices, $a$ and $b$. Without loss of generality suppose $H$ holds $a$. Then $x\sim b$ and $a\sim b$ in $\bar{G}$. So there is a unique $\{a,b\}$ path in $\bar{G}$, namely $\{a,b\}$.
C3: Suppose $H$ holds both the $a$ and $b$ vertices. Then $y\sim a$, $y\sim b$, $y\sim x$ in $\bar{G}$. So there is a unique $\{a,b\}$ path in $\bar{G}$, namely $\{a,y,b\}$.
Therefore there is a unique $\{a,b\}$ path in $\bar{G}$ for arbitrary $a$ and $b$ vertices in all $3$ cases. Therefore $\bar{G}$ is connected.
$\endgroup$ 1
