Skip to main content
5 of 5
edited title
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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?