TAOCP 7.1.1 Exercise 54
Let $S = {u_1, u_2, \ldots, u_k}$ be a strong component in the implication digraph of a 2CNF formula, where each $u_i$ is a literal.
Exercise 54. [20] Let $S = {u_1, u_2, \ldots, u_k}$ be the set of literals in some strong component of a digraph that corresponds to a 2CNF formula as in Fig. 6. Show that $S$ contains both a variable and its complement if and only if $u_j = \bar{u}_i$ for some $j$ with $2 \le j \le k$.
Verified: yes
Solve time: 58s
Solution
Let $S = {u_1, u_2, \ldots, u_k}$ be a strong component in the implication digraph of a 2CNF formula, where each $u_i$ is a literal.
Assume first that $S$ contains both a variable and its complement. Then there exist indices $i$ and $j$ such that $u_i \in S$ and $u_j = \bar{u}_i \in S$. Since a literal is never equal to its own complement, $i \ne j$. Reindex the elements of $S$ so that $u_1 = u_i$. Under this renumbering, $u_j = \bar{u}_1$ and necessarily $2 \le j \le k$. Hence there exist indices $i$ and $j$ with $u_j = \bar{u}_i$ and $2 \le j \le k$.
Conversely, assume there exist indices $i$ and $j$ with $2 \le j \le k$ such that $u_j = \bar{u}_i$. Then both $u_i$ and $\bar{u}_i$ belong to $S$, since $u_j = \bar{u}_i \in S$ by definition of $S$. Thus $S$ contains a variable and its complement.
Both implications establish the equivalence. This completes the proof. ∎