# Verification report — OWR-2489-009 and OWR-2489-004 (Conforti's subtree conjecture, Oberwolfach Report 51/2008)

Verification date: 2026-09-30 (revised the same day after a second independent verification run).

**Verdict.** The answer is no; the conjecture is false for every denominator parameter k ≥ 3. For each k ≥ 3 there are
two explicit unicyclic counterexamples with short hand proofs: G_k on six vertices, and Ĝ_k on seven vertices, which is
normalised (every integral vertex is a pendant vertex with a continuous neighbour). In both, an explicit point lies in
the convex hull belonging to every subtree of the graph, and in the linear relaxation, but violates a facet-defining
inequality by (k−2)/(2k−3). A third, normalised counterexample for k = 3 (a K_{2,3} core with five pendant integral
vertices) is certified exactly by computer. Two independent verification runs (AI-assisted) confirmed the main result.
The second found the proofs correct and one imprecise statement on normalisation; that statement is corrected, and the
other changes it asked for are applied in this version. The complexity question behind the conjecture (record
OWR-2489-008) stays open. The note is unrefereed.

## Statement checked
- **Primary source.** M. Conforti, "Combinatorial mixed-integer programming", abstract in Oberwolfach Report
  51/2008 (*Combinatorial Optimization*, organised by W. Cook, A. Frank and M. Jünger), Oberwolfach Rep. 5 (2008),
  no. 4, pp. 2904–2905, doi:10.4171/OWR/2008/51.
  - The report PDF was read; the display of Conjecture 2 is an intersection over the family 𝒯 of subtrees T of G whose
    integral vertices are exactly the leaves of T.
  - S(G,I) = {x : x_i + x_j ≥ b_ij (ij ∈ E), x_i ∈ Z (i ∈ I)} for a bipartite graph G = (U ∪ V, E); k is the least
    positive integer with k·b integral. Each conv S(T, I_T) is read as a cylinder.
  - Motivation in the source: the conjecture would put the membership problem for conv S(G,I) (Problem 1) in coNP,
    with a single tree as certificate.
  - The source states that the case k = 2 follows from Conforti–Gerards–Zambelli and that the conjecture is open for
    every k ≥ 3.
- **Corpus records.** ulamai/UnsolvedMath, **OWR-2489-004** (status `open`) and **OWR-2489-009** (status `open`; its
  statement asks whether the identity holds for every denominator parameter k, noting k = 2 known and k ≥ 3 open). The
  two records state the same conjecture; the dataset does not link them (neither record refers to the other, and
  OWR-2489-009 has `exact_statement_duplicate_of = null` and `semantic_duplicate_review_pending = true`). Both records
  are answered by the paper.

## Readings
| Reading | Refuted? | Witness |
|---|---|---|
| Conjecture 2 as stated (intersection over 𝒯, cylinders) | yes, every k ≥ 3 | G_k with x^(k); Ĝ_k with x̂^(k) |
| with the linear relaxation P(G) added (the literal form fails trivially otherwise, e.g. K_2 with I = ∅, where no member of 𝒯 has an edge) | yes | the same points lie in P |
| restricted to normalised instances (integral vertices split, CDEW/Di Summa–Wolsey) | yes | Ĝ_k (every k ≥ 3); N (k = 3) |
| intersection over **all** subtrees (any leaves) | yes | x^(k), x̂^(k) lie in the hull of every subtree; so does x̄ for N (all 788 subtrees, second verification run) |
| with the bounds x ≥ 0 (the setting of Conforti–Gerards–Zambelli, there with k = 2) | yes, every k ≥ 3 | G_k, Ĝ_k shifted by +1 (b ↦ b + 2) |
| k = 1 | not refuted: holds once P(G) is included (P is integral) | — |
| k = 2 | not refuted: Conforti's statement via CGZ (whose setting has x ≥ 0); not re-derived here; 3000 random instances gave no gap | — |

## Results in the paper
- **Lemma 2.1** (monotonicity), **Lemma 2.2** (for a unicyclic G, membership in conv S(G − e) for the edges e of the
  cycle gives membership in every subtree hull and in P).
- **Proposition 2.4.** Forests satisfy the conjecture with P (via the decomposition lemma of Conforti–Wolsey–Zambelli,
  Lemma 14 of their revised preprint, and pruning of continuous leaves, Lemma 2.3). So counterexamples need a cycle.
- **Remark 2.5** (normalisation, after CDEW and Di Summa–Wolsey). Splitting an integral vertex into copies preserves
  membership exactly. An edge uv between two integral vertices is replaced by the rounded inequality
  x_u + x_v ≥ ⌈b_uv⌉; removing the edge alone does not preserve membership (one edge uv with u, v integral,
  b_uv = 1/2, x̄ = (3/10, 3/10)). So x̄ ∈ conv S(G,I) if and only if the copied point lies in the hull of the
  normalised instance and the rounded inequalities hold; the conjecture restricted to normalised instances would still
  give coNP. Splitting z turns G_k into a tree. Self-contained proofs of both identities: Corollary 5.6.
- **Section 3.** G_k: U = {p,q,t}, V = {m,w,z}, I = {t,w,z}; b_pm = 1/k, b_pz = 0, b_qm = (k−1)/k, b_qw = (k−1)/k,
  b_qz = 0, b_tm = 0.
  - Lemma 3.2: F_k = k(p+q+m+z) + t + w ≥ k on S(G_k, I) (case analysis).
  - Lemma 3.3 / Table 1: explicit convex combinations (2–3 points, weights λ = (k−2)/(2k−3), μ = 1/(2k−3)) of
    x^(k) = (0, (k−1)(k−2)/(k(2k−3)), −(k−2)/(2k−3), (k²−k−1)/(k(2k−3)), (k−1)/(2k−3), 0) in each of the four spanning
    trees G_k − e.
  - Theorem 3.4: F_k(x^(k)) = λk + μk + λ(k−1) = k − (k−2)/(2k−3) (row qz of Table 1). Lemma 3.5: F_k ≥ k is a facet
    (hand proof).
- **Section 4.** Ĝ_k: z continuous, new integral leaf s on z (b_sz = 0). Lemma 4.2: H_k = k(p+q+m+2z+s) + t + w ≥ k
  (reduction to Lemma 3.2). Lemma 4.3: membership via the linear map ι. Theorem 4.4, Lemma 4.5 (facet). Remark 4.6:
  family (67 subtrees, 9 members, 3 maximal), nonnegativity variant (x ≥ 0, with k ≥ 3).
- **Section 5.** Exact validity certificates: a lifted difference system Λ (for any positive integer k with kb
  integral), Lemma 5.1 (lifting), Lemma 5.2 (CWZ Remark 1), Proposition 5.3 (nonnegative multipliers ⇒ valid
  inequality). Remark 5.4: the instance N (k = 3), c·x̄ = 223/9 < 25 ≤ min over conv S(N), with x̄ in P and in all 116
  family hulls (in fact in all 788 subtree hulls). New in this version: Proposition 5.5, a self-contained proof that
  the projection of Λ is conv S(G,I) (so every valid inequality has a certificate); up to a change of variables, Λ is
  the CDEW extended formulation as described at the end of Section 2 of the CWZ preprint. Corollary 5.6 derives the two
  identities of Remark 2.5 from it.

## Computations (exact; scripts and outputs in reproducibility/)
- **Author** (`lead/`).
  - `check_certificates.py` (standard library only, a few seconds): Table 1 and its image under ι for 3 ≤ k ≤ 200,
    linear relaxations, values of F_k and H_k, facet points and ranks; brute-force enumeration of subtrees and families
    (G_k: 39/7; Ĝ_k: 67/9; N: 788/116); the reduction of Lemma 4.2 on random points; the certificates of
    Proposition 5.3 for F_k and H_k (3 ≤ k ≤ 20, each with α = k) and for N (α = 25, 26 nonzero multipliers), with the
    rows rebuilt from the instance data; Lemma 5.1 tested on boxes; the 116 convex combinations for N.
    Output: ALL CHECKS PASSED (rerun from a fresh extraction of `source.zip` for this version: identical output).
  - `make_certificates.py`: finds the certificates by LP (HiGHS), converts them to rationals, re-verifies them exactly
    (deterministic output).
  - `ghat_numeric_check.py`: exact convex combinations of x̂^(k) for all 67 subtrees of Ĝ_k and LP values, 3 ≤ k ≤ 8.
  - `search_norm_two_leaves.py` (evidence only): no gap for normalised instances with a 4-cycle core and two pendant
    integral vertices, k = 3, 4, 5.
- **Finder** (`claimant/`). Exact certificates for all 39 subtrees of G_k (3 ≤ k ≤ 12); parametric certificates
  (k ≤ 60); grid/brute-force minima; facet rank (k ≤ 60); CBC: min F_k = k (2 ≤ k ≤ 8); HiGHS LP values for the fixed
  objective F_3 (3 over conv S(G_k,I) against 3 − 1/k over the right-hand side of (1), 3 ≤ k ≤ 12, floating point);
  extended-formulation LP versus MILP on 300 random instances (0 mismatches); the search and reduction that found G_k;
  controls (k = 2: 3000 random instances, no gap; at most 5 vertices, k ≤ 6: 6400 instances, no gap).
- **First independent verification run** (`verifier/`, AI-assisted, separate code). Re-derived Lemma 3.2 by hand;
  re-enumerated subtrees and family of G_k; combinations for T1 and T2 exact for 3 ≤ k ≤ 300; exact minimum of F_k
  on a box for k ≤ 7; re-checked the finder's 39 certificates; found the normalised instance N (and a k = 5 instance,
  not used in the paper) and its 116 membership certificates.
- **Second independent verification run** (`independent_run_2/`, AI-assisted; its own library `ref1_lib.py`, written
  from the text of the paper before any of the author's scripts was read; exact `fractions` arithmetic throughout;
  standard library only).
  - Validity by a method independent of Λ (exact minimum over S by enumerating the (1/k)-grid on the V-side inside a
    rigorously derived box, U-side greedy): min F_k = k for 2 ≤ k ≤ 16, min H_k = k for 2 ≤ k ≤ 14, min c·x = 25 over
    S(N); plain brute force without the greedy step for G_3, G_4, Ĝ_3.
  - Membership and non-membership by a second method independent of Λ (the extended formulation Q_I of CWZ Theorem 3,
    solved by an exact two-phase simplex, with threshold rounding into explicit convex combinations re-checked point by
    point): x^(k) in the hulls of all 39 subtrees of G_k and of the four G_k − e (3 ≤ k ≤ 7); x̂^(k) in the hulls of all
    67 subtrees of Ĝ_k (3 ≤ k ≤ 6); x̄ in the hulls of all 116 family members of N, and of all 788 subtrees of N;
    x^(k) ∉ conv S(G_k), x̂^(k) ∉ conv S(Ĝ_k), x̄ ∉ conv S(N) (exact infeasibility). A sanity test confirms that the
    CWZ lift of every (1/k)-integral point of S in the test boxes satisfies its implementation of Q_I.
  - Exact LP (information): min F_k over P ∩ (family hulls) = k − (k−2)/(2k−3), attained at x^(k) (k = 3, 4, 5), and
    the same for H_k on Ĝ_k (k = 3, 4); min over conv S = k.
  - Λ rebuilt from the paper: the printed k = 3 certificate (α = 3); Lemma 5.1 on all (1/k)-integral points of S in
    boxes (17,245 / 34,878 / 2,341 / 285,906 points for G_3, G_4, Ĝ_3, N). The author's `certificates.json` re-verified
    with its own code (36 flow certificates; N: 26 nonzero multipliers, α = 25; the 116 convex combinations; certified
    family = enumerated family).
  - Table 1 and ι-images (3 ≤ k ≤ 200), facet ranks 5 and 6 (3 ≤ k ≤ 100), subtree and family enumeration, the CWZ
    structural assumptions A1/A2 for G_3, Ĝ_3, N, and Lemma 4.2 on 16,000 random points.
  - Rerun of the previous release from fresh extractions of its `source.zip`: all outputs identical (three search
    scripts differ only in printed running times), `certificates.json` regenerated byte for byte.
  - For this version the eight scripts were rerun in the release layout: outputs identical to the recorded ones, apart
    from elapsed-time lines and relabelled messages (see `reproducibility/README.md`).

## Independent verification
### First run (2026-09-30)

| Item | Verdict |
|---|---|
| Source fidelity (report PDF re-fetched, checksum matches; the display is an intersection) | CONFIRMED |
| Correctness (Lemma 3.2 re-derived; enumeration; combinations; solver cross-checks) | CONFIRMED |
| Answers the question as intended | CONFIRMED (negative), with the normalisation caveat below |
| Novelty | CONFIRMED as far as can be checked (no refutation found in print) |
| Classification | PAPER_CANDIDATE, with required fixes |

Required fixes and how they were applied:
1. *Normalised variant.* Splitting z turns G_k into a tree, so G_k alone does not refute the conjecture for normalised
   instances. **Applied:** new normalised family Ĝ_k for every k ≥ 3 with hand proofs (Section 4); the verification
   run's instance N is now certified exactly (Section 5, Remark 5.4).
2. *coNP wording.* **Applied:** the paper says that the proposed certificate, a single subtree of G or of a
   normalisation of G, does not exist in general, and that the complexity of Problem 1 (OWR-2489-008) remains open.
3. *Literature.* **Applied:** CWZ (MOR 2010; revised preprint of November 2009 read) does not restate the conjecture and
   proposes a different one (Conjecture 26 there); the Conforti–Cornuéjols–Zambelli survey (4OR 2010) is silent;
   Di Summa–Wolsey (SIOPT 2011 = CORE DP 2010/63), Section 5, give an example indicating that mixing sets are
   insufficient, a tree instance consistent with the conjecture; the normalisation result used is Proposition 3 of
   Di Summa–Wolsey, a consequence of the CDEW extended formulation.
4. *k ≤ 2.* **Applied:** k = 1 holds only with P added; k = 2 is Conforti's statement derived from CGZ (setting with
   x ≥ 0, odd I-paths possibly ending at continuous nodes), not re-derived.
5. *Tree case.* **Applied:** Proposition 2.4 with a proof that cites CWZ Lemma 14 for splitting at integral vertices;
   no vertex- or edge-minimality is claimed beyond "a cycle is needed".
6. *Corpus notice.* Recorded below as a suggestion (no public action was taken).

### Second run (2026-09-30)
The second run read the source (report PDF from EMS Press), checked every proof by hand, recomputed every numerical
claim with its own code (above), reran the release, and repeated the literature search.

| Item | Verdict |
|---|---|
| Statement fidelity (S(G,I), k, 𝒯 and the intersection as in the source; CWZ assumptions hold; all readings refuted) | CONFIRMED |
| Proofs (all checked by hand) | CORRECT; one imprecise statement in Remark 2.5 (fix 1) |
| Computations (two exact methods independent of Λ, exact LP, own re-check of the certificates) | CONFIRMED |
| Release (rerun from `source.zip`) | reproduces identically or byte for byte |
| Novelty | no prior refutation or later discussion found |
| Presentation | good; minor fixes |
| Fatal error | none |

Required fixes and how they were applied:
1. *Remark 2.5, membership.* The previous text said that normalisation preserves membership; this is false once an
   edge between two integral vertices is removed (one edge uv with u, v integral, b = 1/2, x̄ = (3/10, 3/10)).
   **Applied:** Remark 2.5 now says that splitting preserves membership exactly, and that each removed edge uv between
   integral vertices is replaced by the inequality x_u + x_v ≥ ⌈b_uv⌉; the counterexample is given; the coNP remark is
   restated with this correction (a violated rounded inequality or a single subtree would certify non-membership).
2. *Citations of Di Summa–Wolsey.* **Applied:** the three claims were re-checked against CORE Discussion Paper 2010/63
   (October 2010, 25 pages), obtained anonymously on 2026-09-30 from
   https://cdn.uclouvain.be/public/Exports%20reddot/core/documents/coredp2010_63web.pdf (532,218 bytes, sha256
   58281e828a6f7d1e486392b5c2b9333ae5efeccc10943df8ed484c5b09e2c4ed; identical to the Internet Archive capture of
   14 August 2017 of the same file). All three are confirmed:
   - Proposition 3 (p. 4), attributed there to CDEW: conv(N ∩ {Dv ≤ β}) = conv(N) ∩ {Dv ≤ β} for a network-dual
     set N and a network-dual system on the integer variables with integral β;
   - steps (i) and (ii) of Section 2 (p. 5): removing inequalities involving only integer variables and putting them
     back with an integer right-hand side, and making every integer variable occur in at most one inequality;
   - Section 5 (p. 19): the example has continuous s1, s2 and integer x1, x2, y1, y2 with constraints linking s1–x1,
     s1–x2, s2–y1, s2–y2, s1–s2, a tree whose leaves are exactly the integer variables. The paper now says that the
     example "indicates" (their word) that mixing sets are not enough, rather than "shows".
   The text copy of this discussion paper used in the first verification round contains the same passages.
   In addition, the paper now proves both normalisation identities itself: Proposition 5.5 (projection of Λ equals
   conv S(G,I), proof as suggested) and Corollary 5.6 (step (i) with the rounded inequality; the splitting identity).
3. *Survey of Conforti, Cornuéjols and Zambelli.* **Applied:** the paper lists "a preprint (February 2010)" among the
   versions read and says that the published 4OR version was not seen. The preprint (dated November 2009, revised
   February 2010; 45 pages) was fetched anonymously from http://integer.tepper.cmu.edu/webpub/ExtFor-Feb2010.pdf,
   which redirects to https://www.andrew.cmu.edu/user/gc0v/webpub/ExtFor-Feb2010.pdf (439,045 bytes, sha256
   f9110164b5421ebe940ca911cc14a454eeaa41ff406e87161d29c59e946d8b7f). Its Section 8, "Variable discretization"
   (pp. 38–42), defines S(G,I), gives the extended formulation (Theorem 8.3, Remarks 8.1–8.7) and does not mention the
   conjecture; the only conjecture mentioned in the survey is one of Yannakakis.
4. *This report.* **Applied:** the corpus-records sentence now says neutrally that the two records state the same
   conjecture and that the dataset does not link them; the sentence on the survey is updated (item 3); the Zenodo copy
   and the checksums are regenerated.
5. *Remark 4.6(b).* **Applied:** it now says that both examples also refute the bounded variant with x ≥ 0 (the
   setting of CGZ, but with k ≥ 3).

Optional suggestions applied: the one-vertex subtrees of K_2 (no member of 𝒯 has an edge); "as Conforti notes, this
problem is in NP"; wording of the proof of Lemma 4.5; the HiGHS run of the finder is described with its fixed objective
F_3; Theorem 3.4 evaluated via row qz of Table 1; one sentence on earlier results of the conjectured shape (CWZ
Theorem 23 for the continuous mixing set with flows, read in the revised preprint; the two classes of Di Summa–Wolsey,
per their abstract); the relation of Λ to the CDEW formulation (checked against the text of CWZ, Section 2, and by
comparing the rows by computer for G_3, G_4, G_5, Ĝ_3, Ĝ_4 and N, `lead/cwz_correspondence_check.py`); the textbook
of Conforti, Cornuéjols and Zambelli (2014) is listed as not checked; the count of web searches is updated to three;
the LP optimality of x^(k) and x̂^(k) and the 788 subtree hulls for N are stated as computations of the second run.
As a further sanity check, `lead/normalisation_identities_check.py` tests both identities of Corollary 5.6 on random
points of small instances by exact membership tests.

## Relation to the literature, novelty and scope
- **Read in full:** Conforti's abstract (the source); CGZ (preprint of the IPCO 2007 paper); the revised preprint
  (November 2009) of Conforti–Wolsey–Zambelli, MOR 35 (2010) (https://personal.lse.ac.uk/zambelli/papers/mix-tree.pdf,
  sha256 de2acf0d2dc82c0b9904a630982833049d18968d30ce8d998875ff6b66d3139e); Di Summa–Wolsey, CORE DP 2010/63
  (published in SIOPT 21 (2011); copy as in item 2 above); a preprint (November 2009, revised February 2010) of the
  survey of Conforti, Cornuéjols and Zambelli, 4OR 8 (2010) (copy as in item 3 above).
- **Results of the conjectured shape.** CWZ Theorem 23 (revised preprint): the hull of the continuous mixing set with
  flows is the intersection, over the partitions (X, T), of the hulls of relaxations X^(X,T). Di Summa–Wolsey: for two
  network-dual sets whose continuous variables are linked by a bidirected path, the hull is an intersection of hulls
  of mixing sets. Neither refutes or discusses Conforti's conjecture.
- **Searches (September 2026, anonymous, logged).** arXiv API, zbMATH (including later works of Conforti, Di Summa,
  Wolsey, Zambelli and Gerards), OpenAlex (works citing CGZ, CDEW, CWZ and the report), Crossref (all DOIs verified),
  three web searches (finder, first and second verification runs). Nothing reports a counterexample, a proof, or any
  later discussion of the conjecture; the proposers apparently dropped it without refuting it in print.
- **Caveats.** The published versions of CWZ, Di Summa–Wolsey and the survey, and the 2014 textbook of Conforti,
  Cornuéjols and Zambelli, were not seen. This negative search is not a proof of priority.
- **Scope.** The note refutes Conjecture 2 for every k ≥ 3 in all readings listed above. It does not settle the
  complexity of optimising over S(G,I) (OWR-2489-008), does not re-prove the case k = 2, and does not determine the
  least size of a counterexample (random experiments found none with at most five vertices, and none among normalised
  4-cycle instances with two pendant integral vertices).

## Suggested corpus update (not performed)
Mark OWR-2489-004 and OWR-2489-009, which state the same conjecture, as solved (negative answer: false for every
k ≥ 3, also for normalised instances), citing the eventual DOI of this note. The `literature_assessment` of
OWR-2489-004 currently describes Goemans' conjecture on single-source unsplittable flows, which appears to be a copy
error. OWR-2489-008 remains open.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/