Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

up vote 11 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|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|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

 
discard

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.