Bipartite graphs

Julio

Member
Let $G$ be a bipartite graph with bipartition $U$ and $W$ such that $|U|\ge |W|$. Is it true that $\alpha(G) =|U|$?

The answer is false, but I don't know how to justify it. I would appreciate any help.

caffeinemachine

Well-known member
MHB Math Scholar
If you do not assume connectedness then the simplest example where $\alpha(G)$ is more than $|U|$ is when there are no edges. But one can constrcut such exampels even with connectedness.