# Verification report — AMR-029-0044 (EGRES Open: independent arborescences in acyclic digraphs)

Verification date: 2026-10-11.

**Verdict.** The note gives a **complete answer, yes**, to the question in the reading stated below; every statement
it makes is proved, and the scope is as follows.
- **Settled.** For every finite acyclic digraph (parallel arcs allowed), all roots r_1, …, r_k (not necessarily
  distinct) and all convex sets U_i containing r_i: independent r_i-arborescences F_i with V(F_i) = U_i exist if and
  only if at every vertex v there are pairwise openly node-disjoint paths from r_i to v, one for each i with
  v ∈ U_i; both conditions are equivalent to a local condition, a bipartite matching problem at every vertex
  (Theorem 1.1, Corollary 1.2).
- **Reading.** The open node-disjointness of the EGRES problem page is used on both sides: for the paths and for
  the root paths of the arborescences. This is the reading of the paper of Frank, Fujishige, Kamiyama and Katoh
  (2013). The EGRES page "Arborescence" says "internally node-disjoint" and does not define it. With different
  notions on the two sides the equivalence fails for trivial reasons (Remark 2.3).
- **Also proved.** The same equivalence for the weaker disjointness of Kamiyama's survey (Proposition 7.1), which
  gives the same conditions on digraphs without parallel arcs (Lemma 7.2); and the equivalence when the condition
  on arcs is dropped on both sides (Section 2.2).
- **Not claimed.** That the method is new; priority. No answer to the question was found in the literature
  accessible to us; a search that finds nothing is not a proof of novelty.
- **Not read.** Huck (1995) and Whitty (1987), cited through other texts; the dissertation of A. Hoyer (2019),
  of which only the abstract was read; two technical-report versions of the 2013 paper from 2009. Huck's paper
  of 1999 was read completely after verification run 2. See the last but one section.
- **Computations** are tests and no part of the proof. One enumeration of run B is incomplete (8 vertices, 3
  sets, tight instances) and is reported as such; run 2 completed this range with one program of its own.
- **State of verification.** Two independent AI-assisted verification runs (A, B) examined the first written
  version; a further AI-assisted verification run (run 2) examined the text of the note line by line and with
  its own programs. None of them found an error in a proof or a counterexample. After run 2, Huck's paper of
  1999 was read completely and the passages of the note on it were rewritten; no definition, statement or proof
  was changed (see "After run 2" below). This is not peer review.

The note is unrefereed.

## Statement checked
- **Problem page.** EGRES Open (Egerváry Research Group), "Independent arborescences in acyclic digraphs",
  https://lemon.cs.elte.hu/egres/open/Independent_arborescences_in_acyclic_digraphs .
  - The page asks, for an acyclic digraph with root-nodes r_1, …, r_k and convex sets U_i containing r_i, whether
    independent r_i-arborescences F_i with V(F_i) = U_i exist if and only if for each node v there are openly
    node-disjoint paths P_i from r_i to v, one for each i with v ∈ U_i, where openly node-disjoint means
    edge-disjoint with V(P_i) ∩ V(P_j) = {v} ∪ ({r_i} ∩ {r_j}).
  - It states that the problem was proposed by S. Fujishige, N. Kamiyama and N. Katoh, and lists as known the
    case of one root, the case in which every node lies in at most two of the sets, and the combination of both
    for general digraphs. The page was last modified on 25 March 2015; in the list of the collection the problem
    stands under the open problems.
  - Access: the page and the pages "Arborescence", "Convex node set" and the list of problems were read on
    11 October 2026 (08:43 and 09:07 UTC), when the results were first written down, and saved. Later on the
    same day the site did not respond; run A read the problem page once more, and otherwise the verification
    runs read the saved copies of the same day. The history and discussion tabs of the page were not seen.
- **Source of the question.** A. Frank, S. Fujishige, N. Kamiyama, N. Katoh, "Independent arborescences in directed
  graphs", Discrete Math. 313 (2013) 453–459, doi:10.1016/j.disc.2012.11.006, read completely (7 pages) in the copy
  on the first author's web page. The question is its Question 2 (p. 454), posed for arbitrary digraphs,
  restricted to acyclic digraphs. Used for the conventions: finite digraphs without loops, parallel arcs allowed;
  roots not necessarily distinct; convex sets; r-arborescences; internal disjointness of distinct walks, used on
  both sides of Question 2; the "only if" part is called immediate there. Its Theorems 2, 4 and 6 are the three
  known cases.
- **Corpus record.** ulamai/UnsolvedMath, AMR-029-0044 (dataset version 1.6.0). Its statement is a verbatim copy of
  the statement of the EGRES page.

## Readings
| Reading | Answer | Where |
|---|---|---|
| Open node-disjointness of the EGRES problem page on both sides (the reading of the 2013 paper) | yes | Theorem 1.1, Corollary 1.2 |
| "Distinct walks" (2013 paper) in place of "edge-disjoint" (EGRES page) | the same notion, except for two trivial paths at a common root; read literally there, both sides would fail as soon as two roots coincide; the 2013 paper does not use it so | Lemma 2.2 and the paragraph after it |
| The weak notion of Kamiyama's survey (a path may pass through the root of another one) on both sides | yes | Proposition 7.1 |
| The condition on arcs dropped on both sides | yes (replace every arc by k parallel copies) | Section 2.2 |
| Independence as a condition on vertices only, path condition with the condition on arcs | the equivalence fails trivially (one arc, two equal roots) | Remark 2.3(a) |
| Weak independence with the path condition of the page, or the converse mixture | the equivalence fails trivially (three vertices, two parallel arcs) | Remark 2.3(b) |
| Under every reading | from the path condition of the page: arborescences independent in the strongest of these senses; the "only if" part whenever both sides use the same notion | Section 2.2 |
| A path without arcs (v = r_i) | imposes no condition; only the indices of J(v) matter at v | Section 2.1 |
| Sets with a vertex not reachable from the root | both conditions fail; reachability is not assumed | Section 2.1 |
| Sets that are not convex | the statement is false (smallest instance: three vertices, one set) | Section 4 |
| Digraphs with directed cycles | not the question; false for one root, spanning arborescences and k ≥ 3 by Huck (1995), taken from the 2013 paper and from EGRES TR-2009-04 | Sections 2.3 and 4 |
| Steiner version (paths required only to terminals; Bérczi–Kovács, TR-2011-04, Theorem 2.8) | another problem; not treated | Section 4 |
| Digraphs without parallel arcs | the weak and the strong conditions coincide | Lemma 7.2 |

## Results in the paper
- **Theorem 1.1, Corollary 1.2.** (ARB), (PC) and (LOC) are equivalent; the answer to the question is yes.
- **Lemma 2.2, Remark 2.3.** Given the condition on vertices, two paths to v have a common arc if and only if they
  are the same non-trivial path (then a single arc from a common root). Two examples for mixed readings.
- **Definition 3.1, Remark 3.2.** Admissible assignments, (A1)–(A3); (LOC) at a vertex is a bipartite matching
  problem: a tail that is the root of an index of J(v) serves only the indices with this root, one parallel arc
  each; every other tail serves at most one index.
- **Lemma 3.3.** (ARB) ⟹ (PC) ⟹ (LOC); convexity gives (A1).
- **Lemma 3.4.** For a generic partial potential and an admissible assignment of minimum cost, the strict
  inequalities (1) have a solution: the cycles of the exchange digraph Δ have non-negative length by minimality
  (rotation of the arcs along a cycle) and non-zero length by genericity.
- **Lemma 3.5 and the construction.** Genericity can be kept (finitely many hyperplanes); the potential is built
  along a topological order and satisfies (P).
- **Lemmas 3.6 and 3.7.** The chosen arcs form r_i-arborescences on the sets U_i, and they are independent: for
  two indices i, j the function f_i − f_j increases along F_i and decreases along F_j inside U_i ∩ U_j (case a),
  and (A3) excludes a path through the other root (cases b, c).
- **Remark 3.8.** (a) Admissible assignments with a potential satisfying (P) are a certificate for (ARB);
  (b) without minimality of the cost the set X can be empty.
- **Section 4.** Where convexity, acyclicity and finiteness are used; two instances without convexity; the Steiner
  version.
- **Section 5.** One root (Theorem 4 of the 2013 paper, condition (1)); the two theorems of Huck (1999):
  Theorem 1 (one root, spanning arborescences, parallel arcs allowed; restated in TR-2009-04, Theorem 5.3, and
  TR-2011-04, Theorem 1.2(ii)) and Theorem 2 (pairwise distinct roots in a simple acyclic digraph; restated in
  TR-2009-04, Theorem 5.1); at most two sets per vertex (Theorem 6 of the 2013 paper, conditions (4) and (5)).
  For two sets the potential is the classical ordering argument. The note does not claim that the admission of
  parallel arcs is new for one root.
- **Section 6.** A worked example on 10 vertices with three roots and a certificate (Table 1).
- **Proposition 7.1, Lemma 7.2.** The weak notion; simple digraphs.
- **Lemma 8.1.** If all tight instances with at most n vertices and k sets satisfy (ARB), then (LOC) implies (ARB)
  for all instances with at most n vertices and at most k sets.

## Computations (sanity checks; programs and outputs in reproducibility/)
No proof depends on a computation. A search that finds no counterexample is not a proof.
- **Programs written with the note** (`writing_stage/`, standard library). `check_note.py` (about 10 seconds; TOTAL
  failures: 0): the worked example as printed (convexity, (PC) by enumeration of paths, (LOC), the certificate of
  Table 1, the six inequalities at vertex 9, the root paths, 6 families of independent arborescences, 5 on the
  vertices 0 to 8 of which 2 cannot be extended, the costs at vertex 9, uniqueness of the minimum); the instances
  of Remark 2.3 and of Section 4; Remark 3.2 on 20,000 random local configurations. `tables_from_outputs.py`
  recomputes every total quoted in Section 8 from the recorded outputs.
- **Programs with which the results were first obtained** (`original/`): 142,663,839 instances, of which 15,675,286
  satisfy (PC), among them 2,596,738 three-set instances. Exhaustive: n ∈ {3, 4} with up to 3 parallel arcs and
  k ≤ 4 (3,713,044); n = 5 simple, k ≤ 4 (2,813,016); n = 5 with up to 2 parallel arcs, k = 3 (12,442,412); n = 6
  simple, 2 ≤ k ≤ 4 (121,272,546). Random: 1,900,000 general, 162,821 arc-minimal three-set, 360,000 tight
  instances. (PC) and (LOC) agree everywhere, and with (ARB) wherever it was searched; the construction succeeded
  on every instance with (LOC). 1,305,650 families of admissible assignments: the 1,102,205 for which a
  floating-point linear programme finds a potential are independent. Weak variant: 1,471,647 instances.
- **The incident of the first run.** With random points whose numerators lay between −10^6 and 10^6 only, the
  construction stopped twice on tight instances with a cycle of length exactly 0, an exact tie between two
  admissible assignments: the random stand-in for the generic choice failed, not the theorem (both instances
  satisfy (ARB); no cycle of negative length occurred). The program was changed to 64 random bits with a new start
  after a tie, all runs were repeated, and no tie occurred again. Run B recomputed both ties and reproduced the
  effect with 5 and 8 random bits.
- **Verification run A** (`verification_run_A/`): its own definitions and its own construction. 63,122,895
  instances with all convex sets (n ≤ 4 with up to 2 parallel arcs and k ≤ 3; n = 4, k = 4; n = 5 simple, k = 3),
  for both notions; 15 of the 16 exhaustive rows of `original/` reproduced with the same counts (42,457,616
  instances); 2,000,000 random and 614,746 arc-minimal random instances with a vertex in three sets with three
  different roots; Lemma 2.2 on 141,722 pairs of paths; step (ii) of Lemma 3.4 on 2,531,200 abstract local
  configurations; Remark 3.8(a) on 654,881 families; the conditions of the 2013 paper on 3,523,097 instances;
  sets that are not convex; Lemma 7.2 on 4,772,828 instances.
- **Verification run B** (`verification_run_B/`): its own definitions, written before it opened the programs of
  `original/`. 739,798,070 instances by enumeration (up to 6 vertices, up to 6 sets), 30,951,388 with (PC), all of
  them with (ARB); (LOC) compared on 16,776,860 of them and on 39,338,592 instances with arbitrary convex sets;
  the weak notion on 39,072,260 instances; its construction verified on 1,995,229 instances of the enumeration,
  in 646,452 runs on random instances and on 64,858 arc-minimal instances with 14 to 32 vertices; Lemma 3.4 with
  arbitrary potentials (X non-empty for all 2,418,919 assignments of minimum cost, empty for 1,814,005 of
  4,135,458 others); 2,291,311 random instances; a local search over 1,618,157 tight instances.
- **Tight instances** (run B, Lemma 8.1): all tight instances with 3 sets on 5, 6, 7 vertices, 4 sets on 4, 5, 6
  vertices and 5 sets on 5 vertices satisfy (ARB) (those on fewer vertices were tested as intermediate steps);
  this covers every instance with at most 3 sets and 7 vertices, 4 sets and 6 vertices, or 5 sets and 5 vertices.
  The program of run B counts an instance once for every arrangement of its pairs (r, U) in a sequence with
  non-decreasing roots: 49,210,316 in this count, 14,270,699 as multisets of pairs (run 2). For 8 vertices and 3
  sets the enumeration of run B is **incomplete**: 20 of 24 parts (770,506,630 instances in its count, none
  without (ARB)); the other four parts were stopped without result.
- **Verification run 2** (`independent_run_2/`): its own definitions and its own construction, written from the
  sources and from the statements of the note. All 45,403,215 instances with all convex sets for n ≤ 4
  with up to 2 parallel arcs and k ≤ 3 and for n = 5 simple, k = 3: (ARB), (PC), (LOC) decided from the
  definitions, strong and weak and with the condition on arcs dropped on both sides; Remark 3.2 against
  Definition 3.1 at 224,377,521 vertices; the construction with a potential verified to be generic on all
  389,276 instances with (LOC) (weak form: 391,845), each output tested for (P) and with explicit paths. 100,000
  arc-minimal random instances with pairwise different roots (6 to 13 vertices, 3 to 6 sets; all tight);
  300,000 random instances built from the degenerate situations and 150,000 general ones (on random instances
  with neither (PC) nor (LOC), where (ARB) fails by the easy implication, the search for a family was bounded;
  it ended without a family on 364,885 and was stopped at the bound on 592; weak notion: 361,351 and 745). Its own enumeration of
  tight instances reproduces the seven totals of run B and is complete for 8 vertices and 3 sets as well
  (421,315,865 instances as multisets, 953,971,137 in the count of run B, none without (ARB); one program only).
  Lemma 2.2 on 141,722 pairs of paths; the comparisons of Section 5; the reduction of Lemma 8.1 on 519,379
  reductions; the worked example as printed. No disagreement in any run.
- **Re-runs.** Run B re-ran 28 runs of the programs of `original/` (18,967,988 instances and the smaller tests);
  all outputs are identical to the recorded ones up to running times. On 2026-10-11, at the writing,
  `reproducibility/run_quick.sh` was run from an extracted copy of the archive: 67 program runs from all four
  parts, all outputs identical to the recorded ones, or identical up to fields that record running times. Run 2
  repeated this on the package as it was before its corrections (67 comparisons, none different) and, after
  the corrections, on the new package with the quick programs of run 2 added (85 comparisons from all five
  parts; all outputs identical, or identical up to fields that record running times). Details are in
  `reproducibility/README.md` and `reproducibility/RERUN_LOG.txt`.

## Independent verification runs
The results were first obtained with a written proof and the programs in `original/`. Two independent verification
runs, both AI-assisted, followed on the same day; each worked from the sources with its own programs, and neither
had the record of the other. Run A examined the statement, the proof line by line, the hypotheses, the special
cases and the weak variant; run B examined the statement, tested the theorem and the construction with its own
implementations, read and re-ran the programs of `original/`, and repeated the search of the literature. The note
was written after the two runs.

| Item | Run A | Run B |
|---|---|---|
| Statement and conventions against the sources | CONFIRMED_WITH_FIXES (wording only: the reading of "independent"; "edge-disjoint" against "distinct"; the corollary and the status sentence) | CONFIRMED_WITH_FIXES (the attribution of the definition of independence; the mixed reading) |
| Lemma 2.2 | proved by run A | proved by run B independently |
| Remark 2.3(b) | found by run A | found by run B independently |
| The condition on arcs dropped on both sides | proved by run A | not its part |
| Lemma 3.3 | CONFIRMED | re-derived, no gap |
| Lemma 3.4 | CONFIRMED; implicit steps to be written out | re-derived, no gap; confirmed by a direct test with arbitrary potentials |
| Lemma 3.5 and the construction | CONFIRMED; one sentence on the quantifier to be added | re-derived, no gap; its implementation never failed other than by an exact tie, and never with 64 random bits |
| Lemmas 3.6 and 3.7 | CONFIRMED; implicit steps to be written out | re-derived, no gap |
| Theorem 1.1 | CONFIRMED | CONFIRMED by its tests (no counterexample); the proof was not its part |
| Remark 3.2 | one sentence required | one sentence required |
| Hypotheses: convexity, acyclicity, the Steiner version | examined; the statement is false without convexity (instances found by its search), and the proof uses convexity at exactly the places named | not its part |
| The implication from (LOC) to (PC) | proved directly, by Menger's theorem, for one root and for two sets | no disagreement in its tests |
| Special cases | examined; the form of Huck's theorem in the sources to be stated exactly | the local condition is known in the two acyclic cases of the 2013 paper |
| Worked example | reproduced in every detail | reproduced |
| Proposition 7.1 (weak notion) | CONFIRMED_WITH_FIXES (to be written out as a proposition with a complete proof) | re-derived, no gap; no disagreement in its tests |
| Lemma 7.2 | found and proved by run A | found and proved by run B; its proof is the one in the note |
| Lemma 8.1 and the enumeration of tight instances | not its part | due to run B |
| Programs of `original/` | 15 of 16 exhaustive rows reproduced with its own code | CONFIRMED: read, no error that could make a test vacuous; 28 outputs re-run and identical; the account of the incident is accurate |
| Literature, novelty | no answer and no counterexample found; the method was not found in the texts read; novelty of the method not to be claimed before Huck (1999) and the dissertation of Hoyer are read | CONFIRMED_WITH_FIXES: neither the theorem nor a counterexample nor the method was found; the account of the literature to be completed; three items to be read or checked before publication |

Neither run found a wrong statement, a gap, or a counterexample.

**Verification run 2 (an independent run on the written note).** After the note had been written, a further
AI-assisted verification run examined the text as written. It had the records of runs A and B at hand and opened them only for their summaries
and lists of corrections, after it had checked the proofs; it wrote its programs before it opened the programs
of the package (with one exception named in `reproducibility/independent_run_2/README.md`).

| Item | Run 2 |
|---|---|
| Statement and conventions against the sources (EGRES pages in the saved copies; the 2013 paper, all 7 pages) | CONFIRMED |
| Lemma 2.2, Remark 2.3, the reading without the condition on arcs | CONFIRMED (re-derived; tested) |
| Lemma 3.3 | CONFIRMED |
| Lemma 3.4, with (i), the rotated family, the cost identity, the cyclic configuration, the strictly feasible point | CONFIRMED; one sentence on (A2) made exact |
| Lemma 3.5, the quantifier over later vertices, absence of circularity | CONFIRMED |
| Lemmas 3.6 and 3.7, all cases, every use of convexity and acyclicity, the common arc | CONFIRMED |
| Degenerate situations (coinciding roots, identical pairs, a root inside another set, v = r_i, sets {r}, parallel arcs from a common root) | examined one by one; no gap; 300,000 random instances built from them |
| Remark 3.2 | CONFIRMED; wording made exact ("correspond to") |
| Lemma 8.1 and what the enumeration proves | CONFIRMED; the way of counting of the quoted totals had to be stated |
| Section 5 against the sources | CONFIRMED_WITH_FIXES (Huck's abstract; see below) |
| Proposition 7.1, Lemma 7.2 | CONFIRMED |
| Worked example | reproduced from the printed table |
| Cited results | as quoted; DOIs of the five journal articles verified with Crossref |
| Literature, novelty | no answer, no counterexample, the method not found; novelty not certified |

**Corrections required by run 2**, all applied in the note:
1. Huck (1999): run 2 could read the abstract (in the record of the article in the repository CORE); it speaks
   of finite acyclic multigraphs, with trees directed towards one vertex. The sentences "Huck's own formulation
   is not known to us" and "Theorem 1.1 … allows parallel arcs everywhere" were replaced; the note no longer
   presents parallel arcs as new for one root and spanning arborescences; the disclosures then said that only
   the abstract was accessible (abstract, Section 1, Section 5, "Scope and priority", bibliography). They were
   replaced when the paper had been read (see "After run 2").
2. "Scope and priority" said that Theorem 1.1 contains Theorems 2, 4 and 6 of the 2013 paper; Theorem 2 is a
   statement about arbitrary digraphs and is contained only for acyclic ones. Corrected.
3. The totals of tight instances in Section 8 are counts of arrangements, not of instances as defined there;
   the way of counting is now stated and the number of multisets is given.
4. The paragraph "Verification" and Section 8 record run 2.
5. Section 2.3: "the question was open for …" was replaced by what the sources leave open.
6. Lemma 3.4, step (ii), (A2): the symmetry in the two indices is said.
7. Remark 3.2: "correspond to the matchings", with the role of parallel arcs from a tail that is not a root.
8. Proposition 7.1: (P_w) is stated at every vertex.
9. Bibliography: notes on Huck (1999) and on the published version of TR-2009-04.
10. "Scope and priority": the searches of run 2; ten web searches in all.

Not done by run 2: run 2 did not read the text of Huck (1999), which was not accessible to it (the paper was
read afterwards; see "After run 2"); the dissertation of Hoyer was not requested again; the long enumerations of
runs A and B were not repeated as such.

**Corrections required by run A**, all applied in the note (item 6 at first in the form of a disclosure; Huck
(1999) was read after run 2, the dissertation of Hoyer was not):
1. The reading of "independent" is stated: the EGRES page "Arborescence" is quoted with its own words, the reading
   with one notion on both sides is presented as that of the 2013 paper, and the mixed readings are shown to fail
   (Sections 1 and 2.2, Remark 2.3).
2. Lemma 2.2 with its proof replaces a parenthesis; the literal wording of the 2013 paper for coinciding roots is
   discussed after it.
3. Corollary 1.2 names the notion and the trivial paths; the status is worded as "listed as open on the EGRES page;
   the paper proves three cases and does not treat the general acyclic case" (abstract, Section 1, "Scope and
   priority").
4. Steps written out: in Lemma 3.4, that (i) applies to every index on a cycle of Δ, and that the minimum need not
   be unique; in the definition of genericity and in the construction, that the condition concerns every vertex w,
   also later ones; in Lemma 3.7, that w ∈ U_i ∩ U_j, the case v = r_i, that b ≠ r_j in case b, and the use of
   Lemma 3.6 for F_i in case a; Remark 3.2 with its reason.
5. The weak variant is Proposition 7.1 with a complete proof, in a section of its own that is not needed for the
   answer; Kamiyama's definition is quoted; Lemma 7.2 is added.
6. The note says which texts were not read (at the writing Huck (1999) and the dissertation of Hoyer; now the
   dissertation only), claims neither novelty of the method nor more than "no answer was found", and says that
   for two sets the potential is the classical ordering argument (abstract, Sections 1 and 5, "Scope and
   priority").
7. Huck's theorem is described in the forms in which the two technical reports state it. (At the writing the
   note added that Theorem 1.1 allows parallel arcs and that Huck's own formulation was not known to us; this
   was replaced after run 2 had read the abstract, see correction 1 of run 2, and again when the paper had been
   read, see "After run 2".)
8. (Optional) The reproduction of 15 of the 16 exhaustive rows is reported (Section 8).

**Corrections required by run B**, applied in the note; of item 3, Huck (1999) was read after run 2, and the
rest is met by disclosure:
1. As 1 of run A; in addition the sentence on what holds under every reading (Section 2.2).
2. The account of the literature: the numbers of citing works in four indices; the two versions of 2009; the
   local conditions of the 2013 paper and Lovász's theorem on flames as related work; a plain list of what was
   read ("Scope and priority").
3. Run B asked that, before publication, Huck (1999) be read and the lists of citing works in Google Scholar
   and the two versions of 2009 be checked, and that the absence of Huck (1999) be disclosed if it cannot be
   obtained. Huck (1999) was read completely after run 2 (see "After run 2"). **The other two checks have not
   been made**: the note discloses in "Scope and priority" that the versions of 2009 were not read and that
   Google Scholar was not consulted.
4. The run that was stopped in the first run is named: the general run with seed 5 (Section 8).
5. As 4 of run A for Remark 3.2, with the treatment of parallel arcs.
6. Lemma 7.2, and the remark that only the instances in ranges with parallel arcs test the weak variant beyond
   Theorem 1.1 (Sections 7 and 8).
7. (Optional) The reduction to tight instances and the enumeration are reported (Lemma 8.1, Section 8).

**Changes made when the note was written, after the two runs.** These were not examined by run A or run B in
this form; run 2 examined all of them in the text as written:
- the wording of all proofs in Sections 3 and 7 (the arguments are those examined by run A, with its steps added;
  the proof of Lemma 7.2 is that of run B);
- the argument of Remark 3.2 as a correspondence between admissible assignments and matchings (tested by
  `check_note.py` on 20,000 random local configurations);
- Lemma 8.1 in one direction only; run B had stated the reduction as an equivalence, and the test needs only the
  direction that is proved in the note;
- in Section 5, the comparison with condition (1) of the 2013 paper and the derivation of the case of several
  sources;
- the short form of the argument for the reading without the condition on arcs (Section 2.2);
- the selection of the two instances of Section 4 from those of run A (checked by `check_note.py`);
- the numbers of Section 8, which were recomputed from the recorded outputs by `tables_from_outputs.py`; they
  agree with the numbers of the two runs. Two phrases of the runs were made exact: "348,034 instances in ranges
  with parallel arcs" (not all of these instances have parallel arcs), and the ranges of the enumeration of run B
  (for n = 3 only k ≤ 4).

**After run 2: Huck (1999) read.** A. Huck, "Independent branchings in acyclic digraphs", Discrete Math. 199
(1999) 245–249, was read completely (5 pages) on 11 October 2026, after run 2.
- What the paper contains. Digraphs are finite and may have multiple edges; branchings are directed towards
  their root; two edge-disjoint paths are openly disjoint if every common vertex is an end of both (p. 245). For
  two paths from a vertex to roots this is the open node-disjointness of the EGRES page in the reversed digraph.
  Theorem 1: an acyclic digraph in which every vertex other than t has n pairwise openly disjoint paths to t has
  n pairwise independent spanning t-branchings. Theorem 2, from which Theorem 1 is derived by splitting the root:
  in a simple acyclic digraph with pairwise distinct vertices t_1, …, t_n in which every other vertex has
  out-degree at least n there are pairwise independent t_i-branchings B_i, where B_i contains all vertices
  except the t_j with j ≠ i. The proof is by induction on n: Lemma 1 gives one branching and a numbering of
  the other vertices that is topological for the branching and, in reversed order, for the rest of the digraph.
  The paper contains no convex sets, no roots inside other sets and no potential.
- What this means for the note. No theorem of the note is affected. The case of pairwise distinct roots with
  arborescences that contain all vertices except the other roots, which the note had from TR-2009-04,
  Theorem 5.1 (attributed to Huck there), is Theorem 2 of Huck's paper itself. Both theorems of Huck are special
  cases of Theorem 1.1 (Section 5). The proof in Huck's paper is of the kind described in the note for the
  other texts read (one arborescence is removed at a time, with an ordering of the vertices).
- What was changed in the note: one sentence of the abstract; in Section 1 the sentences on the known cases and
  on the proofs read; in Section 2.3 the sentences on Huck's theorems; in Section 5 the two paragraphs on Huck's
  theorems, now written from the paper; in Section 8 the statements on what was read ("Verification", "Scope
  and priority"), and the number of web searches; the note of the bibliography entry. No definition, statement or
  proof of the note was changed. **These passages were not examined by the runs A, B and 2.**

## Relation to the literature, novelty and scope
- **Searches (11 October 2026).** The works citing the 2013 paper in OpenAlex, Semantic Scholar, Crossref and
  OpenCitations (one in each; where it is named, it is Kamiyama's survey of 2014); the works citing Huck (1999) in
  OpenAlex (10) and Semantic Scholar (19), by titles and available abstracts; queries to the arXiv API, zbMATH
  Open, OpenAlex and Crossref; the titles of the EGRES technical reports of 2009–2026; twelve web searches in all
  (two when the results were first written down, three in each of the runs A and B, one at the writing, one in
  run 2, two after run 2). Run 2 repeated the queries to the arXiv API (8 requests), OpenAlex (the works citing
  the 2013 paper: one; those citing Huck 1999: the same ten), Crossref and zbMATH Open, and read the abstract of
  Huck (1999) in the record of the article in the repository CORE. After run 2, OpenAlex was asked once more
  (one work citing the 2013 paper; 24 works for the phrase "independent arborescences", none of them on the
  question).
  - No answer to the question and no counterexample was found.
  - Known cases of the question: Theorems 2, 4 and 6 of the 2013 paper (Theorem 2 for arbitrary digraphs); the
    two theorems of Huck (1999) for acyclic digraphs (Theorem 1: one root, spanning arborescences, parallel arcs
    allowed; Theorem 2: pairwise distinct roots in a simple digraph, arborescences that contain all vertices
    except the other roots), restated in Bérczi–Frank, EGRES TR-2009-04, Theorems 5.3 and 5.1, and
    Bérczi–Kovács, EGRES TR-2011-04, Theorem 1.2.
  - A local condition equivalent to the path condition is in the 2013 paper in its two acyclic cases. Related,
    for one root in arbitrary digraphs: Lovász's theorem on flames, known to us only from the abstract of
    arXiv:2502.10052.
- **What was read.** The 2013 paper completely; Section 3.3 of N. Kamiyama, "Arborescence problems in directed
  graphs: theorems and algorithms", Interdiscip. Inform. Sci. 20 (2014) 51–70; Section 5 of TR-2009-04; TR-2011-04
  except its figures; the EGRES pages named above in copies of the same day; A. Huck, "Independent branchings
  in acyclic digraphs", Discrete Math. 199 (1999) 245–249, completely (after run 2). Bibliographic data of the five
  journal articles were checked with Crossref (at the writing and again by run 2) and that of the preprint with
  the arXiv API; the title and the year of the dissertation of Hoyer were taken from the announcement of its
  defense. A published version of TR-2009-04 (RIMS Kôkyûroku Bessatsu B23, 2010) is listed in zbMATH; the
  report was read, not that version.
- **What was not read.** A. Huck, J. Graph Theory 20 (1995) 235–239, and R. W. Whitty, J. Graph Theory 11 (1987)
  349–358: not requested; what the note says about them is taken from Huck (1999), the 2013 paper and
  TR-2009-04. A. Hoyer, "On the independent spanning tree conjectures and related problems", dissertation,
  Georgia Institute of Technology, 2019: not accessible to us; only the abstract was read. Two technical-report versions of the 2013 paper from 2009, listed in OpenAlex. The
  figure of TR-2011-04 that carries its Theorem 2.8. The preprint arXiv:2502.10052 beyond its abstract.
  A. Frank's book "Connections in Combinatorial Optimization" (2011) and the lists of citing works in Google
  Scholar were not consulted.
- **Caveats.** Huck's proof (1999), on which the proofs of the 2013 paper (Theorem 4) and of the survey are based
  according to these texts, removes one branching at a time with topological numberings and contains no
  potential. By its abstract the dissertation of Hoyer proves cases of the independent spanning tree conjectures
  by embedding vertices or edges in a simplex; it was not read and could contain ideas related to the method of
  the note. For two sets the method is the classical ordering argument. This negative search is not a proof of
  priority.
- **Scope.** The note answers the question for acyclic digraphs in the reading stated above. It says nothing new
  about digraphs with directed cycles, about the Steiner version, or about sets that are not convex. No priority
  is claimed, and no claim is made that the method is new.

## 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/