# 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! – ivt 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. – ivt 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

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.

-