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

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .