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

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.


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


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.

Tags:

Graph Theory

Related

How to solve $\binom{n}{1}^2+2\binom{n}{2}^2 + 3\binom{n}{3}^2 + 4\binom{n}{4}^2+\cdots + n\binom{n}{n}^2$? Prove $\ln\frac{p}{q}\leq \frac{p-q}{\sqrt{pq}}$ for $0<q\leq p$ A finite graph with exactly two vertices with odd degree must have a path joining them. Evaluating $\int_a^b \arccos\left(x\,/\sqrt{(a+b)x-ab\,}\,\right)\,\mathrm {d}x$ assuming $0<a<b$ How to integrate $\int_0^\infty\frac{x^{1/3}dx}{1+x^2}$? If $I+J=R$, where $R$ is a commutative rng, prove that $IJ=I\cap J$. Deriving even odd function expressions Limit of $\arctan(x)/x$ as $x$ approaches $0$? Ease-in-out function A question about an $n$-dimensional subspace of $\mathbb{F}^{S}$. If coprime elements generate coprime ideals, does it imply for any $a,b\in R$ that $\langle a\rangle+\langle b\rangle=\langle \gcd (a,b)\rangle$? Why does $PSL(2,\mathbb C)\cong PGL(2,\mathbb C)$ but $PSL(2,\mathbb R) \not\cong PGL(2,\mathbb R)$?

Recent Posts