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

  • Context: MHB 
  • Thread starter Thread starter Julio1
  • Start date Start date
  • Tags Tags
    Graphs
Click For Summary
SUMMARY

The discussion centers on the relationship between the independence number $\alpha(G)$ of a bipartite graph $G$ and the size of its bipartition $U$. It is established that the statement $\alpha(G) = |U|$ is false. The simplest counterexample occurs when there are no edges in the graph, leading to $\alpha(G)$ being greater than $|U|$. Additionally, examples can be constructed even when the graph is connected, further disproving the initial assumption.

PREREQUISITES
  • Understanding of bipartite graphs and their properties
  • Knowledge of graph theory concepts such as independence number
  • Familiarity with graph connectivity
  • Basic combinatorial reasoning
NEXT STEPS
  • Study the properties of bipartite graphs in depth
  • Learn about the independence number and its implications in graph theory
  • Explore examples of connected and disconnected bipartite graphs
  • Investigate counterexamples in graph theory to solidify understanding
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in the properties of bipartite graphs and independence numbers.

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

MHB Understanding Two Graph Theory Problems
  • · Replies 2 ·
Replies
2
Views
2K
MHB How many new branches will the complement graph of a deleted edge have?
  • · Replies 11 ·
Replies
11
Views
2K
MHB Proving K-Extendability of a Bipartite Graph
  • · Replies 1 ·
Replies
1
Views
1K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Some basic questions on Graph theory
  • · Replies 2 ·
Replies
2
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K
Comp Sci Shortest path problem in bipartite graph
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad How Does Quantum Negativity Vary with Partial Transposes in Bipartite Systems?
  • · Replies 1 ·
Replies
1
Views
1K
MHB The Recursion Theorem .... Searcoid, Theroem 1.3.24 .... ....
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Help understanding conditional expectation identity
  • · Replies 1 ·
Replies
1
Views
2K