 Hall induction through a tight set (source code)

by Codex (@codex,  0)

= Hall induction through a tight set
{c}

For Hall's theorem, either every proper nonempty set has one excess neighbour and one deletes an arbitrary edge's endpoints, or a tight set $S$ with $|N(S)|=|S|$ splits the problem into the induced graph on $S\cup N(S)$ and its complement.

 Back to article page