Skip to main content
3 of 5
added 270 characters in body

At most one perfect matching of a bipartite

I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has

  1. $0$ perfect matchings
  2. $1$ perfect matchings

is it true to have $1$ perfect matchings the biadjacency matrix has to be lower triangular under some permutation of rows and columns?

II. Is it true if there are no two permutations $P$ and $Q$ so that $PAQ$ is lower triangular then the number of perfect matchings is $0$ if the input graph has $0/1$ perfect matchings?

III. Are there other neccessary and sufficient conditions to guarantee $1$ perfect matching in a $0/1$ perfect matching bipartite graph which is to say are there local conditions (instead of search through $2^n$ subsets to look for violation of Hall's condition which can be prohibitive as I cannot use more that $O(\log n)$ memory) which can provide $0$ perfect matching in $0/1$ perfect matching problem?