A Necessary and Sufficient Hall Condition for Hypergraphs

Abstract

We prove a necessary and sufficient Hall condition for a family $A=(A_e)_{e\in E(G)}$ of hypergraphs indexed by the edges of a forest \(G\). This restriction on the index graph is sharp. The loop-only case recovers the classical Hall's Theorem with multiplicities for arbitrary finite set systems, while the loopless case shows that full rainbow matching is polynomial time solvable under this forest structure, although the problem is NP-complete in general. As another application, we prove every $5$-tough chordal graph is Hamilton-connected, improving toughness bounds of $18$ for Hamiltonicity (1998) and $10$ for Hamilton-connectedness (2017).

Disclosure

“tiplicity version of the full rainbow matching problem. Taking qe = 1 for every color e gives the full rainbow matching case. 5. Acknowledgments Claude Opus was used to search for references. AI tools were used to refine the writing after the draft was completed. References [1] Ron Aharoni and Penny E. Haxell. “Hall’s Theorem for Hypergraphs”. In: Journal of Graph Theory 35.2”

PDF page 16

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T05:08:34.114200Z

Structural counts