Given a graph $G = (V, E)$, the complement of G is the graph $G'$ defined on the same vertex set $V$ , however, an edge is present in $G'$ provided that it is not in $G$. Prove by induction that if $G$ is not connected, then $G'$ must be connected.
Asked
Active
Viewed 383 times
0
-
This question asked for a proof of the same result, though it did not ask for a proof by induction. – Andrew Uzzell Mar 26 '13 at 09:49
1 Answers
1
HINT: Suppose that $G$ is a minimal counterexample: neither $G$ nor $G'$ is connected, but the result is true for all graphs with fewer vertices than $G$. If $\deg(v)=0$ for all $v\in V$, $G'$ is connected, and if $G$ is complete, then $G$ is connected, so there is at least one vertex $v\in V$ such that $$0<\deg(v)<|V|-1\;.$$ Let $H$ be the graph that remains when you remove from $G$ the vertex $v$ and all edges incident at $v$. By hypothesis at least one of $H$ and $H'$ is connected. There is at least one vertex $w$ in $H$ such that $vw$ is an edge of $G$, and there is at least one vertex $u$ in $H$ such that $vu$ is an edge in $G'$. (Why?) Use this fact to show that if $H$ is connected, then so is $G$, and if $H'$ is connected, so is $G'$. In either case this contradicts the assumption that $G$ is a counterexample to the theorem.
(Again, you can easily rephrase this as a traditional proof by induction.)
Brian M. Scott
- 616,228