\(1,2\) 番目の条件を以下のように緩和した場合を考えます。

• 空集合からはじめて \(i=1,2,\dots,N\) の順に「 \(A_i,B_i\) のいずれかを追加するか、いずれも追加しない」ことで得られる集合である。
• 空集合からはじめて \(i=1,2,\dots,N\) の順に「 \(A_i,C_i\) のいずれかを追加するか、いずれも追加しない」ことで得られる集合である。

これらの条件を満たす集合の要素数の最大値は明らかに上界になっており、いわゆるネットワークフローの最大流問題として解くことで求められます。

実はこの上界は達成可能であり、このことは 上記のネットワークフローについて検証することで証明できます。