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.
 
Greetings, I am studying probability theory [non-measure theory] from a textbook. I stumbled to the topic stating that Cauchy Distribution has no moments. It was not proved, and I tried working it via direct calculation of the improper integral of E[X^n] for the case n=1. Anyhow, I wanted to generalize this without success. I stumbled upon this thread here: https://www.physicsforums.com/threads/how-to-prove-the-cauchy-distribution-has-no-moments.992416/ I really enjoyed the proof...

Similar threads

  • · Replies 2 ·
Replies
2
Views
2K
Replies
11
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 1 ·
Replies
1
Views
1K