§3.1, eq. (17) — fractional Berge–Tutte formula [SU97, Theorem 2.2.6]
ProvedSpaceReset.Hardness.eq_17graph-theorymatchingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every finite simple graph on vertices,
where and is the fractional matching number.
The identity expresses the two-cut cost of an interval layout through matching deficiency.
Differences from the source:
- encoding: a graph H on k vertices → a simple graph on any finite type V with k = |V|; reason: same statement, vertex set not relabelled
Preamble
import Mathlib import Definitions.Def_SpaceReset_Hardness_Graphs set_option autoImplicit false open Classical
Formal statement
namespace SpaceReset.Hardness
/-- §3.1, eq. (17), p. 22: the fractional Berge–Tutte formula [SU97, Theorem 2.2.6]. -/
theorem eq_17 {V : Type} [Fintype V] [DecidableEq V] (H : SimpleGraph V) :
(Tval H : ℤ) = (Fintype.card V : ℤ) +
(Finset.univ : Finset (Finset V)).sup' Finset.univ_nonempty
(fun S => (isoIn H (Finset.univ \ S) : ℤ) - (S.card : ℤ)) ∧
(Tval H : ℝ) = 2 * ((Fintype.card V : ℝ) - fracMatchingNumber H) := by sorry
end SpaceReset.Hardness
Source
Rinka Miura, STOC 2027 submission #1715 (October 2026), §3.1, eq. (17), p. 22 (cited: Scheinerman–Ullman, Fractional Graph Theory, Theorem 2.2.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.