Let $A$ be biparte graph with P(A) = NP, and let $x$ be a truth assignment such that $x_i$ is 'false' for some $i \in A \subseteq N$. We construct a circuit of size $poly(n)$, where $n = |x| + |x| - 1 + |A|.$ Then $x(e)$ is 'true' iff $e /in G_x$ for some $G_x$ with n vertices, where $G_x<span class="underline"> = \{v \in N: x_v \neq x_u \} </span>$. From the theorem on a graph, we have $|x(e)| \leq O(n)$. So, it takes at most $O(n)^{|x|}$ time to decide if $x$ is a $0-1$ vector. In other words, $O(n)^{|x|} \leq P(G_x) \leq O(n)^{|x|}$ (see, for instance, Theorem 3.1.5 in $L.D. Karpinski and A. Saxena (2013) A combinatorial proof of the graph isomorphism theorem.$.)

We now claim that the bipartite graph, whose adjacency matrix has $\begin{bmatrix} P(A) &amp; \ldots &amp; 0 \\ \vdots &amp; \ddots &amp; \vdots \\ 0 &amp; \ldots &amp; P(A) \end{bmatrix}$ as its submatrix, is the complement of a 3-regular graph:

$G_x = \overline{G_x[u,v]} = (V(G_x), E(G_x) \setminus \{uv\})$

As we have seen, for the proof to go through, we need to show $\forall v,v' \in N : \sum_{u \in V(G_x[v,v'])} w(uv) = 0$. This is an immediate consequence of our construction of $G_x$. For if we consider, $G_x[v,v'] = \{ u \in N : u = v \lor u = v' \}$ (where $\cap /math] and <script type="math/tex"> \cup /math] are the standard sets operations), and observe that <script type="math/tex"> uv \in G_x[v,v'] \implies u = v \lor u = v'$. Therefore, $w(uv) = 0 \implies \sum_{u \in V(G_x[v,v'])} w(uv) = \sum_{u \in V(G_x[v,v'] \setminus \{v\})} w(uv) + \sum_{u \in V(G_x[v,v'] \setminus \{v'\})} w(uv) = 0$, which is true, as required. $\tag*{$ QED