Supplementary Material A Proofs

Let T be a finite set and L be a collection of subsets of T . Then ( T, L) is 2-extendible if For all C D, if D L then C L; Suppose C D L, and x be such that x / C and C { x } L. Then there exists Y D \C such that | Y | k and D \Y { x } L . To check the second condition, let x be an edge ( i,j). If x D, then the condition holds trivially with Y = . Now obviously each column contains at most two nonzero entries.