Bipartite Graphs: Does $\alpha(G) =|U|$?

  • Context:
  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Graphs
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
1 reply · 2K views
Julio1
Messages
66
Reaction score
0
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.
 
Physics news on Phys.org
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.