Welcome to our community

Be a part of something great, join today!

Bipartite graphs

Julio

Member
Feb 14, 2014
71
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
Mar 10, 2012
832
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.