3
$\begingroup$

Given a 3-CNF formula where each variable from variables $x_1,...,x_n$ appears exactly 3 times in different clauses $c_1,...,c_m$, and each clause contains exactly 3 different variables, prove that the formula is satisfiable using Hall's marriage theorem.

Firstly, because each variable appears in 3 different clauses and each clause contains 3 different variables it follows that $n=m$.

We can define $X=\{x_1,...,x_n\}$, $Y=\{c_1,...,c_n\}$ and a bipartite graph $G=(X\cup Y, E)$ where $E=\{(x_i, c_j)|x_i\in c_j\}$.

Let $P$ be a set of clauses, $P \subseteq Y$.

In order to use Hall's theorem I need to prove that $|\Gamma(P)|\ge |P|$, where $|\Gamma(P)|$ means the neighborhood of $P$ (all adjacent vertices) but I'm really not sure how to prove that using graph theoretic formulation of Hall's theorem.

$\endgroup$
  • $\begingroup$ What does it mean $\Gamma(P)$? $\endgroup$ – Taroccoesbrocco Jan 15 '18 at 18:01
  • $\begingroup$ @Taroccoesbrocco I added the explanation in the OP. $\endgroup$ – Yos Jan 15 '18 at 18:03
2
$\begingroup$

You've already set the problem up, and the rest is a classic corollary of Hall's theorem:

Every $k$-regular bipartite graph has a perfect matching.

In case you are unfamiliar: here $k$-regular means that the degree of each vertex is $k$ and a perfect matching is a collection of disjoint edges that covers all the vertices. You have a $3$-regular bipartite graph, and a perfect matching would assign to each clause a unique variable, which you would then set to be true or false to make that clause true.

Proof: Let $P \subseteq Y$. Since the degree of each vertex of $P$ is $k$, there are $|P|\cdot k$ many edges between $P$ and $\Gamma(P)$. But since the degree of each vertex of $\Gamma(P)$ is $k$ and $P \subseteq \Gamma(\Gamma(P))$, there are at most $|\Gamma(P)|\cdot k$ many edges between $P$ and $\Gamma(P)$. This implies that $|P|\cdot k \leq |\Gamma(P)| \cdot k$, or $|P| \leq |\Gamma(P)|$ as desired.

Note that we can apply this result repeatedly: a $k$-regular bipartite graph minus a perfect matching is a $(k-1)$-regular bipartite graph. Thus we can partition the edges of a $k$-regular bipartite graph into $k$ perfect matchings (this is known as a 1-factorization). This means that there are at least 3 ways your 3-CNF is satisfiable!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ so in the matching each clause would be matched to only one variable? more specifically would it be a one-to-one map between clauses and variables? $\endgroup$ – Yos Jan 16 '18 at 9:30
  • 1
    $\begingroup$ Yes. Since the bipartite graph has the same number of vertices on each side (same number of variables as clauses), a perfect matching gives a bijection between the two sides. $\endgroup$ – Bob Krueger Jan 16 '18 at 16:16
  • $\begingroup$ Also why the fact that $P \subseteq \Gamma(\Gamma(P))$ imply that $|P|\le |\Gamma(P)|$? $\endgroup$ – Yos Jan 16 '18 at 16:30
  • 1
    $\begingroup$ There is a step you're missing. There are exactly $|\Gamma(P)| \cdot k$ edges between $\Gamma(P)$ and $\Gamma(\Gamma(P))$, so since $P \subseteq \Gamma(\Gamma(P))$, there are at most $|\Gamma(P)| \cdot k$ edges between $\Gamma(P)$ and $P$. But since there are exactly $|P|\cdot k$ edges between $\Gamma(P)$ and $P$ (see the above argument again), $|P| \cdot k \leq |\Gamma(P)| \cdot k$. $\endgroup$ – Bob Krueger Jan 16 '18 at 17:20
  • 1
    $\begingroup$ @Yos another way of saying what’s happening: the number of edges between $P$ and $\Gamma(P)$ is at most the number of edges between $\Gamma(P)$ and $\Gamma(\Gamma(P))$. The desired inequality follows. $\endgroup$ – Bob Krueger Jan 16 '18 at 20:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.