Cutsets in bipartite graphs *
Richard A. Brualdi, Bryan L. Shader · Linear and Multilinear Algebra · 1993
Let G be a matching-covered, connected bipartite graph. We determine the dimension of the binary vector space which is spanned by the characteristic vectors of perfect matchings of G. We then show that the cutsets of G are those sets F of edges such that ∣F⋂M∣ has the same parity for every perfect matching M of G.