# 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
• That's brilliant. Thank you. Nov 9 '20 at 5:17

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.. Mar 20 '13 at 9:50
• Would the downvoter care to explain? Mar 21 '13 at 0:03

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.

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? 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). 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 :-) 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.

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.

This is another answer, showing 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~a and x~b in G¯ so there is a unique {a,b} path in G¯, namely {a,x,b}. (~ means adjacent)

C2: Suppose H holds one of the two vertices, a and b. Without loss of generality suppose H holds a. Then x~b and a~b in G¯. So there is a unique {a,b} path in G¯, namely {a,b}.

C3: Suppose H holds both the a and b vertices. Then y~a, y~b, y~x in G¯. So there is a unique {a,b} path in G¯, namely {a,y,b}.

Therefore there is a unique {a,b} path in G¯ for arbitrary a and b vertices in all 3 cases. Therefore G¯ is connected.

• Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. here, here, here and here.
– mlc
Apr 3 '17 at 11:24

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:
1. $$V_{n+1}$$ is none off $$\{V_1,V_2,\ldots,V_n\}$$
2. $$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.