Consider a special case of 3SAT in which all clauses have exactly three literals, and each variable appears exactly three times. Show that this problem can be solved in polynomial time. (Hint: create a bipartite graph with clauses on the left, variables on the right, and edges whenever a variable appears in a clause. Use Exercise 7.30 to show that this graph has a matching.)

Firstly, need to design a bipartite graph where all clauses lie on the left side and all the variables lies on the right side of the graph.

Suppose there are total clauses and variables and $m\le n$. Consider the variables w, x, y and z.

Proof:

Firstly, design a bipartite graph for all clauses that lie on the left side and all the variables that lies on the right side of the graph.

From Figure 1, the complete clause is provided below:

$\left(W\vee Y\vee Z\right)\wedge \left(W\vee \neg X\vee \neg Y\right)\wedge \left(X\vee \neg Y\vee \neg Z\right)$

To find out that for any subset of clauses, there cannot be less than variables connected to it.

Thus, find matching between clauses and variables according to Hall’s theorem.

This gives an assignment by which there is at least a literal which holds true in every clause.

Like, W$\leftarrow True,Y\leftarrow True,Z\leftarrow False$, X and can be either true or false.

Hence, the given statement has been proved.