TAOCP 7.2.2.2 Exercise 388
Let $G=(V,E)$ and $G'=(V',E')$, with $|V|=m$ and $|V'|=n$.
Section 7.2.2.2: Satisfiability
Exercise 388. [20] Show that the problems of deciding whether or not a given graph $G$ (a) contains a $k$-clique, (b) can be $k$-colored, or (c) has a Hamiltonian cycle can all be regarded as graph embedding problems.
Verified: no
Solve time: 5m
Solution
Let $G=(V,E)$ and $G'=(V',E')$, with $|V|=m$ and $|V'|=n$. Introduce a Boolean variable $x_{v,v'}$ for every pair $(v,v')\in V\times V'$. The intended meaning is that $x_{v,v'}$ is true exactly when the vertex $v$ of $G$ is mapped to the vertex $v'$ of $G'$.
The variables must satisfy three conditions. First, every vertex of $G$ must have an image. For each $v\in V$, introduce the clause
$$ \bigvee_{v'\in V'}x_{v,v'} . $$
Second, two different vertices of $G$ must not be mapped to the same vertex of $G'$. For every pair of distinct vertices $u,v\in V$ and every $v'\in V'$, introduce the binary clause
$$ \bar{x}{u,v'}\vee \bar{x}{v,v'} . $$
Third, every edge of $G$ must be mapped to an edge of $G'$. For each edge $uv\in E$ and each pair $u',v'\in V'$ such that $u'v'\notin E'$, introduce the binary clause
$$ \bar{x}{u,u'}\vee \bar{x}{v,v'} . $$
Let $F$ be the conjunction of all clauses constructed in these three ways. We prove that $F$ is satisfiable if and only if $G$ can be embedded in $G'$.
Suppose first that $G$ can be embedded in $G'$. Let $f:V\rightarrow V'$ be the corresponding injective map. Assign
$$ x_{v,v'}=1 $$
exactly when
$$ v'=f(v). $$
For every vertex $v\in V$, the clause
$$ \bigvee_{v'\in V'}x_{v,v'} $$
contains the true literal $x_{v,f(v)}$, so every vertex clause is satisfied.
Because $f$ is injective, if $u\ne v$, then $f(u)\ne f(v)$. Therefore no pair of variables $x_{u,v'}$ and $x_{v,v'}$ with $u\ne v$ can both be true. Hence every clause
$$ \bar{x}{u,v'}\vee \bar{x}{v,v'} $$
is satisfied.
Finally, let $uv\in E$. Since $f$ is an embedding, $f(u)f(v)\in E'$. A clause of the third type is generated only for pairs $u',v'$ with $u'v'\notin E'$. Thus the assignment cannot make both $x_{u,u'}$ and $x_{v,v'}$ true in any such clause, and every clause of the third type is satisfied. Therefore $F$ is satisfiable.
Conversely, suppose that $F$ has a satisfying assignment. For every vertex $v\in V$, define $f(v)$ to be a vertex $v'\in V'$ for which
$$ x_{v,v'}=1 . $$
Such a vertex exists because the clause
$$ \bigvee_{v'\in V'}x_{v,v'} $$
must be satisfied.
The binary clauses
$$ \bar{x}{u,v'}\vee\bar{x}{v,v'} $$
ensure that two different vertices of $G$ cannot be assigned the same image. If $u\ne v$ and $f(u)=f(v)=v'$, then both $x_{u,v'}$ and $x_{v,v'}$ would be true, contradicting the clause
$$ \bar{x}{u,v'}\vee\bar{x}{v,v'} . $$
Therefore $f$ is injective.
It remains to show that edges are preserved. Let $uv\in E$. Suppose that $f(u)f(v)\notin E'$. The construction then includes the clause
$$ \bar{x}{u,f(u)}\vee\bar{x}{v,f(v)} . $$
By the definition of $f$, both literals $x_{u,f(u)}$ and $x_{v,f(v)}$ are true, so both literals in this clause are false. This contradicts the assumption that the assignment satisfies $F$. Hence
$$ f(u)f(v)\in E' $$
whenever
$$ uv\in E . $$
Thus $f$ is an embedding of $G$ in $G'$.
The constructed clauses are therefore satisfiable exactly when $G$ has an embedding in $G'$. This completes the proof. ∎