Matroids and graphs
W. T. Tutte · Transactions of the American Mathematical Society · 1959
Proof.By Axiom I (M-X)U{a} meets every FGM.It thus has a dendroid D of Mas a subset.But aED since DC\X?± 0. Hence X = J(M, D,a).(2.2) If D is a dendroid of M then a(D) =dM+l.Proof.If D = 0, then M is a null class and dM= -1.In the remaining case we enumerate the cells of D as cii, • • • , ak and write S0 = (M), 5,-= (217-{oi, • • • , at}) (i = l, ■ ■ ■ , k).It is clear that J(M, D, at)C5,_i and so aiESi-i and Si = (Si-i -{a<}).But dSk= -1 since DC\Sk = 0. Hence 1959] (2.6) K(M,D, b)CM*.Proof.If K(M, D, b)CL(M) choose XCM such that a(XC\K(M, D, b)) = 1 and a(X(~\D) has the least value consistent with this.Write X(~\K(M, D, b) = [c].If e belongs to DC\X but not to K(M, D, b) we have &G7(M, 77, e) and so cG7(7Vf, 77, e).By Axiom II there exists X'CM such that cCX' Q(XVJJ(M, D, e))-{e}.But then a(XT\K(M, D, b)) = l and a(XT\D) <a(XC\D), contrary to the definition of X.Since XC\D9£0 we deduce that cG77 and X = J(M, D, c).But cCK(M, D, b).Hence bCI(M, D, c)=X and a(XC\K(M, D, b))^2, contrary to the definition of X.We deduce that K(M, D, b) CL(M).As no non-null proper subset of K(M, 77, b) is orthogonal to all the sets 7(AT, 77, a) it follows that K(M, D, b) CM*.(2.7)The dendroids of M* are the complements in M of the dendroids of M. Proof.Let 77 be any dendroid of M. Then M-D meets each YCM*, for no non-null subset of 77 is orthogonal to all the sets J(M, D, a).But no proper subset of M -D meets all the sets K(M, D, b).Hence M-D is a dendroid of M*, by (2.6).Conversely suppose 77' is a dendroid of M*.Then M-D' meets each XCM, lor no non-null subset of 77' is orthogonal to all the sets J(M*, 77', a).