Skip to main content
1 of 5

At most one perfect matching of a bipartite

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?

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$?

Are there other neccessary and sufficient conditions to guarantee $1$ perfect matching in a $0/1$ perfect matching bipartite?