9
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ of course. man next time i need to try to think first, before i ask something here. $\endgroup$ – ultrajohn Sep 22 '12 at 21:08

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.