# Given a simple graph and its complement, prove that either of them is always connected.

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.

-

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.

-
Short and simple! This problem took me almost two hours, who knew it's so easy, just had to look at it...Thank you! Definitely accepted! –  user825089 Mar 19 '12 at 19:01
I wonder what we might point out here as a generally useful tactic? –  MJD Mar 19 '12 at 19:28
I think the generally useful tactic here is to actually look at the graph and draw some pictures...I started with writing out complex formulas, but it was a wrong approach to this particular problem. –  user825089 Mar 19 '12 at 19:54

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 ;-)

-
Such a nice proof.. –  muzzlator Mar 20 '13 at 9:50
Would the downvoter care to explain? –  dtldarek Mar 21 '13 at 0:03

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.

-
${}{}{}{}{}$How? –  Aryabhata Apr 19 '13 at 2:32
@Aryabhata, see my further explanation. –  Easy Apr 19 '13 at 2:36
Isn't this just a <strike>convoluted</strike> different way of stating dtldarek's answer? I don't see how talking about the adjacency matrix made it any more easier. In fact, even if your answer didn't have the first two sentences, it would be good enough (and easier IMO). –  Aryabhata Apr 19 '13 at 3:24
@Aryabhata, I think this is more likely to be equivalent to Chris Eagle's proof. But taking the adjacency matrix gives the general idea how the idea pops up. Anyway, eventually they are similar. –  Easy Apr 19 '13 at 3:34
You may be right. I didn't actually read Chris' answer :-) –  Aryabhata Apr 19 '13 at 4:23

----------------SOMETHING WRONG WITH THIS PROOF. I AM TRYING TO FIX IT------------------------

Apart from the above illustrative proofs, an inductive proof exists too.

Let G be a disconnected graph with n vertices, where n >= 2. The complement of G is a graph G' with the same vertex set as G, and with an edge e if and only if e is not an edge of G.

Base case: We know that this is true for n = 2.

Assume that this is true for n <= k, where k is any positive integer. Let this graph be G(k). The complement G'(k) is connected. Let's look at the extra vertex in G(k+1) - call it X. The vertex X is connected to d vertices, where 0<=d<=k+1.
It cannot be connected to k vertices, because then then graph would be connected. In the complement of the graph, X is connected to k-d vertices. X must be connected to at least one other vertex because 1<=k-d<=k. Since the complement of G(k) is connected and X is connected to at least a vertex in G'(k), then the graph G'(k+1) is also connected.

By the inductive hypothesis, this is true for all n that are positive integers.

-
This is not correct. You must start with $G_{k+1}$ and remove a vertex. Not add $X$ to $G_k$. You basically are missing the proof that any disconnected $G_{k+1}$ can be constructed from some disconnected $G_{k}$, by adding a vertex, or, in other words, there is some vertex in $G_{k+1}$ which can be deleted and the graph will still remain disconnected. –  Aryabhata Apr 19 '13 at 1:09
I dont know...I think I have the case covered when I say that the vertex can be connected to even 0 vertices in G. –  sd_93 Apr 19 '13 at 2:08
Here is a proof that every connected graph with at least $3$ vertices has a triangle. True for $n=3$. Suppose true for all $n \le k$. Now given $G_k$, add a vertex $X$ to get $G_{k+1}$. Since $G_k$ already has a triangle, so does $G_{k}$, and we are done. Where is the mistake? –  Aryabhata Apr 19 '13 at 4:55
Oh. Right. Yeah. But then, how do I ensure that I delete a vertex which disconnects the graph because only when the graph is disconnected will the hypothesis apply. –  sd_93 Apr 19 '13 at 5:21
Right. You start with $G_{k+1}$ which is disconnected. Now you have to find a vertex $X$ in $G_{k+1}$ whose deletion will give a disconnected graph, and then you can apply the hypothesis. Suppose you delete a vertex, and you get a connected graph. You can add it back and delete some other vertex... –  Aryabhata Apr 19 '13 at 5:24

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.

-