Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.6 — (D,S,π) has an M-basic packing of arborescences iff π is M-independent and (D,S,π) is M-connected

Proved
BasicPackArb.Main.theorem_1_6

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

arborescencematroidp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1packing

Let D=(V,A)D=(V,A)D=(V,A) be a finite digraph (parallel arcs allowed), SSS a finite set, π:S→V\pi:S\to Vπ:S→V a placement of the elements of SSS at vertices, and MMM a matroid on SSS with rank function rMr_MrM​. Write SX=π−1(X)S_X=\pi^{-1}(X)SX​=π−1(X) and Sv=π−1(v)S_v=\pi^{-1}(v)Sv​=π−1(v), and ρD(X)\rho_D(X)ρD​(X) for the number of arcs entering XXX.

An MMM-basic packing of arborescences in (D,S,π)(D,S,\pi)(D,S,π) is a family (Ts)s∈S(T_s)_{s\in S}(Ts​)s∈S​ of pairwise arc-disjoint arborescences in DDD, TsT_sTs​ rooted at π(s)\pi(s)π(s) and not necessarily spanning, such that for every vertex vvv the set {s∈S: v∈V(Ts)}\{s\in S:\ v\in V(T_s)\}{s∈S: v∈V(Ts​)} is a base of MMM.

Theorem 1.6. There exists an MMM-basic packing of arborescences in (D,S,π)(D,S,\pi)(D,S,π) if and only if

  1. π\piπ is MMM-independent: SvS_vSv​ is independent in MMM for every v∈Vv\in Vv∈V; and
  2. (D,S,π)(D,S,\pi)(D,S,π) is MMM-connected:
ρD(X) ≥ rM(S)−rM(SX)for all non-empty X⊆V.\rho_D(X)\ \ge\ r_M(S)-r_M(S_X)\qquad\text{for all non-empty }X\subseteq V.ρD​(X) ≥ rM​(S)−rM​(SX​)for all non-empty X⊆V.

With MMM the free matroid on SSS, ∣S∣=k|S|=k∣S∣=k, and every element placed at one vertex rrr, this is Edmonds' theorem on kkk arc-disjoint spanning arborescences rooted at rrr. Through Frank's orientation theorem it also yields Katoh and Tanigawa's characterization of matroid-based rooted-tree packings in undirected graphs.

Formalization Note The packing is a family T : S → Arborescence D with IsBasicPacking D π M T, indexed by SSS (so equal single-vertex arborescences at a vertex are distinct members). Arborescences are sub-digraphs given by a vertex set, an arc set inside AAA and a root, with root in-degree 000, in-degree 111 elsewhere, and every vertex reachable from the root (equivalent to being a directed tree). The rank is Matroid.eRk in N∞\mathbb{N}_\inftyN∞​ and (3) is written rM(S)≤ρD(X)+rM(SX)r_M(S)\le\rho_D(X)+r_M(S_X)rM​(S)≤ρD​(X)+rM​(SX​). The matroid's ground set is the whole root type; no other hypothesis is made.

Preamble
import Mathlib
import Definitions.Def_BasicPackArb_Main_RootedDigraph
Formal statement
namespace BasicPackArb.Main

/-- Theorem 1.6 (p. 3). Let `(D, S, π)` be a digraph with roots and `M` a matroid on `S`. There
exists an `M`-basic packing of arborescences in `(D, S, π)` if and only if `π` is `M`-independent
and `(D, S, π)` is `M`-connected. -/
theorem theorem_1_6 {V Arc S : Type*} [Fintype V] [DecidableEq V] [Fintype S]
    (D : Digraph V Arc) (π : S → V) (M : Matroid S) (hM : M.E = Set.univ) :
    (∃ T : S → Arborescence D, IsBasicPacking D π M T) ↔
      MIndependent π M ∧ MConnected D π M := by sorry

end BasicPackArb.Main
Source
Durand de Gevigney, Nguyen, Szigeti, Basic Packing of Arborescences, arXiv:1207.1985v1, p. 3, Theorem 1.6 (definitions pp. 1–3, (3) on p. 3; proof §2, pp. 4–5)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me