18
$\begingroup$

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$
54
$\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$
  • $\begingroup$ 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! $\endgroup$ – ivt Mar 19 '12 at 19:01
  • 2
    $\begingroup$ I wonder what we might point out here as a generally useful tactic? $\endgroup$ – MJD Mar 19 '12 at 19:28
  • 3
    $\begingroup$ 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. $\endgroup$ – ivt Mar 19 '12 at 19:54
9
$\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$
  • $\begingroup$ Such a nice proof.. $\endgroup$ – muzzlator Mar 20 '13 at 9:50
  • 3
    $\begingroup$ Would the downvoter care to explain? $\endgroup$ – dtldarek Mar 21 '13 at 0:03
1
$\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 sum of two complete graphs. Up to $4$ vertices, the only graphs I have to check are: $$K_1+K_1,\ K_1+K_2,\ K_1+K_3,\ K_2+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$
0
$\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$
  • $\begingroup$ ${}{}{}{}{}$How? $\endgroup$ – Aryabhata Apr 19 '13 at 2:32
  • $\begingroup$ @Aryabhata, see my further explanation. $\endgroup$ – Easy Apr 19 '13 at 2:36
  • $\begingroup$ 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). $\endgroup$ – Aryabhata Apr 19 '13 at 3:24
  • $\begingroup$ @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. $\endgroup$ – Easy Apr 19 '13 at 3:34
  • $\begingroup$ You may be right. I didn't actually read Chris' answer :-) $\endgroup$ – Aryabhata Apr 19 '13 at 4:23
0
$\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$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – mlc Apr 3 '17 at 11:24
-1
$\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:
    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.
$\endgroup$

protected by Saad Mar 7 at 15:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.