I'm aware this result holds for simple graphs:
Given a simple graph and its complement, prove that either of them is always connected.
Does it hold for directed and not strongly connected graphs?
Asked
Active
Viewed 292 times
0
-
What are your thoughts? – bof Aug 15 '18 at 00:40
-
Note that, if there is a counterexample, then there is a counterexample with only $3$ vertices. – bof Aug 15 '18 at 00:41
-
Suppose the digraph $D$ is not strongly connected, and its complement $\overline D$ is not connected. Then there are two vertices $u,v$ such that there is no directed path from $u$ to $v$ in $D,$ and there is a vertex $w$ such that there is no undirected path from $u$ to $w$ in $\overline D.$ Now consider the subgraph of $D$ induced by ${u,v,w}.$ – bof Aug 15 '18 at 00:44
-
Thank you for your comment @bof . I am thinking since $(u,v) \in \overline{D}$ and there is no undirected path between $u$ and $w$, for $\overline{D}$ to be not connected there must be no undirected path between $v$ and $w$. However, this means that $${(u,w),(w,u),(v,w)(w,v)} \subset \overline{D}$$ making $D$ connected. So, by contradiction, $\overline{D}$ must be connected. Am I right? – Simón Ramírez Amaya Aug 15 '18 at 14:52