While learning about graphs, I came across theorem that I don't quite understand, and can't find a proof.

If G is bipartite, and $\det(A) \neq 0,$ then G has a perfect matching. (Given that matrix representation of G is A)

Ps.: I found bits of information, that proof may be connected with Edmonds Theorem, which I cannot find, since Edmonds-Karp Algorithm is way more popular in google ;)

  • $\begingroup$ Do you mean bipartite by chance? $\endgroup$ – Don Thousand Mar 27 at 12:19
  • $\begingroup$ Do you mean "bipartite?" $\endgroup$ – saulspatz Mar 27 at 12:19
  • $\begingroup$ thats exactly what I meant, I corrected this typo ;) $\endgroup$ – Yurkee Mar 27 at 12:28
  • $\begingroup$ It's the next-to-last letter we are asking about. $\endgroup$ – saulspatz Mar 27 at 12:29
  • $\begingroup$ Yes, that's the one where vertices can be divided into two disjoint and independent sets. $\endgroup$ – Yurkee Mar 27 at 12:33

Let the vertices be $[n]=\{1,\dots,n\}.$ The theorem follows from the definition of determinant: $$\det{A}=\sum_{\sigma\in S_n}(-1)^\sigma a_{i\sigma(i)}$$ where $S_n$ is the set of at permutations on $[n].$ Since $a_{ij}$ is $0$ or $1$, there must be a permutation $\sigma$ such that $i$ and $\sigma(i)$ are adjacent for $i\in [n].$

Since $\sigma$ is a bijection, the two bipartition sets have the same cardinality, and the restriction of $\sigma$ to one of them gives a perfect matching.

  • $\begingroup$ Is this proof from the Edmonds Theorem? $\endgroup$ – Yurkee Mar 27 at 13:36
  • 1
    $\begingroup$ Edmonds had a number of theorems. The one I've heard called "Edmonds Theorem" has to do with packing of arborecences, so nothing to do with this. $\endgroup$ – saulspatz Mar 27 at 13:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.