Lemma C.1, p. 44 (first sentence) — a connected acyclic matching network graph has at least n − d + 1 leaves
ProvedConstRegretMatch.Acyclic.lemma_C_1_leavesLet a matching network have agent types and matches, every match using at least two types and every type taking part in at least one match. Suppose its matching network graph (the bipartite type–match incidence graph) is connected and acyclic. Then the number of leaves of (vertices of degree one) satisfies
In Appendix C this count is used to show that some over-demanded queue is a leaf, which is the starting point of the explicit construction of the inverse of the optimal basis.
Formalization Note The inequality is written to avoid natural-number subtraction. Leaves are counted among all vertices of ; since , match vertices never are leaves, so is the number of types that take part in exactly one match.
import Mathlib import Definitions.Def_ConstRegretMatch_Acyclic_Network
namespace ConstRegretMatch.Acyclic
/-- Lemma C.1, p. 44 (first sentence; proof pp. 46–47): if the matching network graph `𝒢` of a
matching network with `n` agent types and `d` matches is connected and acyclic, then the number of
leaves (vertices of degree one) of `𝒢` is at least `n - d + 1`, written without subtraction. -/
theorem lemma_C_1_leaves {n d : ℕ} (N : MatchingNetwork n d)
(hconn : (networkGraph N).Connected) (hacyc : (networkGraph N).IsAcyclic) :
n + 1 ≤ (leaves (networkGraph N)).card + d := by sorry
end ConstRegretMatch.Acyclic
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.