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.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Back
Top