We say that a Boolean formula $$ is in $2-CNF$ if it is a conjunc$-$

tion of clauses, each of which contains exactly two literals. In

class, we showed that the satisfiability problem for the formulas

in $3-$CNF is NP$-$complete. In this problem, we will show that

the satisfiability problem for $2-CNF$ formulas is in P $.$

First, we notice that any clause with two literals can be writ$-$

ten as an implication in exactly two ways. For example, $(pvvnotq)$

is equivalent to both $(qp)$ and $(notp$notq$),$ while e$.$g$.(pvvq)$

is equivalent to both $(notpq)$ and $(notqp).$

For any $2-CNF$ formula $,$ define the directed graph $G_{}$ to

be the graph whose vertices are all literals that occur in $$ and

in which there is an edge from literal $x$ to literal $y$ if$,$ and only

if$,$ the implication $(xy)$ is equivalent to one of the clauses in

$.$

$($a$)$ If $$ has $n$ variables and $m$ clauses, give an upper bound

on the number of vertices and edges in $G_{}.$

$($b$)$ In Boolean logic, it can be proved that $$ is unsatisfiable

if$,$ and only if$,$ there is a literal $x$ such that there is a

path in $G_{}$ from $x$ to notx and a path from notx to $x.$ Give

an algorithm for verifying that the graph $G_{}$ satisfies this

property. What is the complexity of your algorithm?

$($c$)$ From $($b$),$ deduce that there is a polynomial time algorithm

for testing whether a $2-$CNF formula is satisfiable.