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

  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Graphs
AI Thread Summary
In a bipartite graph G with bipartition U and W, where |U| ≥ |W|, the claim that the independence number α(G) equals |U| is false. A simple example demonstrating this is a bipartite graph with no edges, where α(G) exceeds |U|. Furthermore, it is possible to construct examples with connectedness that also show α(G) can be greater than |U|. The discussion emphasizes the need for justification of these claims. Understanding the relationship between the independence number and the sizes of the bipartite sets is crucial in graph theory.
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.
 

Similar threads

Back
Top