A question about bipartite graphs and maximal independent (stable) sets Here's an excerpt from an article:

My question is: why are the conjectures 1 and 2 equivalent for non-connected bipartite graphs? For example, if there are only 2 vertices connected by an edge in a graph, the first conjecture implies those are the ones that belong to at most half maximal stable sets, whereas second permits (in theory) for other vertices to hold that property.
 A: For non-connected bipartite graphs, the two bipartition classes aren't uniquely determined, so it's less clear how to interpret the conjecture.
But the second conjecture is equivalent to the first if we say:

Conjecture 2'. Let $G$ be a finite bipartite graph with bipartition classes $X,Y$ and at least one edge. Then each of $X$ and $Y$ contains a vertex belonging to at most half of the maximal stable sets.

Suppose that $G$ is a bipartite graph such that in each connected component, only one or possibly no bipartition class contains an at-most-half vertex. Then define $X$ by picking a side with no at-most-half vertices from each connected component, and let $Y$ be its complement. This choice of $X$ and $Y$ will contradict Conjecture 2'.
Therefore there must be a connected component $C$ such that both $X \cap C$ and $Y \cap C$ contain an at-most-half vertex. By looking at a path between these vertices, we can find an edge whose endpoints are both at-most-half vertices, and obtain Conjecture 1.

We can even reduce to the case of

Conjecture 3. Let $G$ be a finite connected bipartite graph with at least two vertices. Then each bipartition class contains a vertex belonging to at most half of the maximal stable sets.

To get conjecture 2' from conjecture 3, let $G$ be any finite bipartite graph with at least one edge. Begin by applying conjecture 3 to any connected component $C$ of $G$, finding vertices $x$ and $y$.
Then note that any maximal stable set of $G$ has the following structure: a maximal stable set in $C$, and a maximal stable set in the rest of the graph. So when we go from $C$ to $G$, all counts of maximal stable sets (containing $x$, containing $y$, and with no restrictions) are simply multiplied by the number of maximal stable sets in the rest of the graph. This does not affect the at-least-half property, so $x$ and $y$ are also the vertices that satisfy Conjecture 2'.
