# At most one perfect matching of a bipartite graph

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?

Regarding your other questions, the graphs with zero perfect matchings are characterized as those that fail Hall's condition. Note that even though there are $$2^n$$ candidates, a set that fails Hall's Condition can be found in polynomial time.
• The second question has constraints of $0/1$ mateching. I think I. is similar to II. in the constrained $0/1$ matching problem. Jun 12 at 13:16