Counterexamples to Conforti's Subtree Conjecture for Mixed-Integer Bipartite Covers

For a bipartite graph G = (U ∪ V, E), a set I ⊆ U ∪ V and rationals b_ij, let S(G,I) = {x ∈ R^(U∪V) : x_i + x_j ≥ b_ij (ij ∈ E), x_i ∈ Z (i ∈ I)}, and let k be the least positive integer with kb integral. In the 2008 Oberwolfach report on combinatorial optimization, Conforti conjectured that conv S(G,I) is the intersection of the hulls conv S(T, I ∩ V(T)) over the subtrees T of G whose integral vertices are exactly their leaves. This would place the membership problem for conv S(G,I) in coNP. He noted that the case k = 2 follows from work of Conforti, Gerards and Zambelli, and that the conjecture was open for every k ≥ 3. We show that it fails for every k ≥ 3. For each such k we give two unicyclic counterexamples. One has six vertices. The other has seven, and in it every integral vertex is a pendant vertex with a continuous neighbour, so the standard normalisation of such sets (splitting integral vertices) does not remove it. In both, an explicit point lies in conv S(T, I ∩ V(T)) for every subtree T of G, but violates a facet-defining inequality of conv S(G,I) by (k − 2)/(2k − 3). The proofs are short and by hand. We also describe exact validity certificates based on an extended formulation, and use them to certify a further normalised counterexample for k = 3. The complexity of the membership problem remains open. This is an unrefereed note.