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.

7 Answers 7

54

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.

  • 0
    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!2012-03-19
  • 2
    I wonder what we might point out here as a generally useful tactic?2012-03-19
  • 3
    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.2012-03-19
9

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

  • 0
    Such a nice proof..2013-03-20
  • 3
    Would the downvoter care to explain?2013-03-21
1

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.

0

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.

  • 0
    ${}{}{}{}{}$How?2013-04-19
  • 0
    @Aryabhata, see my further explanation.2013-04-19
  • 0
    Isn't this just a convoluted 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).2013-04-19
  • 0
    @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.2013-04-19
  • 0
    You may be right. I didn't actually read Chris' answer :-)2013-04-19
0

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.

0

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.

  • 1
    Please use proper formatting to enhance readability; for some basic information about writing math at this site see e.g. [here](/help/notation), [here](//meta.math.stackexchange.com/q/5020), [here](//meta.stackexchange.com/a/70559) and [here](//meta.math.stackexchange.com/q/1773).2017-04-03