Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?

share|cite|improve this question
up vote 12 down vote accepted

Given a bipartite graph $G = (U,V,E)$ and a maximum matching $M$ of $G$, via Konig's Theorem we see that $|M| = |C|$ where $C$ is a minimum vertex cover for $G$. Your statement is merely an upper bound on the size of the possible matching, not a strict equality.

The image on the wikipedia page provides a nice counterexample to your claim. We see that $|M| = 6$, while $\min(|U|,|V|) = 7$.

enter image description here

However, in the case of a complete bipartite graph $K_{n,m}$ your statement holds.

share|cite|improve this answer

No. For example, consider the case where the two sides are disconnected $|E| = 0$ or the case where a large group of nodes are all connected to the same single node:

$U = u_1, u_2, ..., u_n$

$V = v_1, v_2, ... , v_n$

$E = u_1v_1, u_2v_1, ... u_nv_1,$ $ v_1u_1, v_2u_1, ... v_nu_1$

share|cite|improve this answer
of course. man next time i need to try to think first, before i ask something here. – ultrajohn Sep 22 '12 at 21:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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