The Union Closed Sets Conjecture (or Frankl conjecture) is described in this link: https://en.wikipedia.org/wiki/Union-closed_sets_conjecture.

It is known that this problem has an equivalent form in terms of graphs.

Namely: Frankl conjecture is equivalent to assertion that in any graph $G=(V,\mathcal{E})$, such $|\mathcal{E}|\ge 1$, there exists two adjacent vertices that each of them belongs to at most half of the maximal independent sets.

But here is the problem:

Imagine the following graph $G=(V,\mathcal{E})$. Where :

$V = \{1,2,3\}$ and $\mathcal{E}=\{\{1,2\},\{2,3\}\}$

The only maximal independent set is $\{1,3\}$

Let's take any two vertices, for instance $1,2$. We see that $1\in\{1,3\}$ so "$1$" belongs to more than half of the maximal independent sets. That contradicts the conjecture.

However i strongly believe that i made some mistakes.

Where is mistake?

Thank you in advance.


$\{2\}$ is also a maximal independent set - no vertices can be added to it without creating an edge.


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.