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

  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Graphs
Click For 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.
 
Hello, I'm joining this forum to ask two questions which have nagged me for some time. They both are presumed obvious, yet don't make sense to me. Nobody will explain their positions, which is...uh...aka science. I also have a thread for the other question. But this one involves probability, known as the Monty Hall Problem. Please see any number of YouTube videos on this for an explanation, I'll leave it to them to explain it. I question the predicate of all those who answer this...

Similar threads