Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$.
Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are the only two maximum independent sets of $V$?
Suppose that $G=(V,E)$ is a connected bipartite graph with $|V|=N$ and vertex set bipartition $V = A \cup B$ such that $|A|=|B|$.
Assume that $\alpha(G) = N/2$. Is it always true that $A$ and $B$ are the only two maximum independent sets of $V$?
Copyright © 2021 JogjaFile Inc.
No. Consider a path with $4$ vertices, Say $a-b-c-d$. Then $A=\{a,c\},B=\{b,d\}$ and $\{a,d\}$ are all independent sets of size $2$.