Vtyjkyuk

(Don't confuse this question with that one about maximum stable sets.)

The answer is positive for finite graphs of course. In infinite graphs the matter becomes interesting. Let's revisit the definitions first.

A (simple) graph is a pair $G=(V,E)$, with $V$ being the set of vertices and $E=binomV2$ being the set of unordered pairs of $V$. For vertices $v,win V$ we write $vw:=v,win E$ and say $v$ and $w$ are adjacent.

A subset $S$ of $V$ is called stable iff for any $v,win S$ we have $vwnotin E$, i.e. no two vertices of $S$ are adjacent. We call such a subset a stable set of $G$.

A stable set $S$ of $G$ is called maximal iff for any $vin Vsetminus S$ holds that $Scupv$ is no stable set of $G$ anymore.

In the finite case every graph has a maximal stable set because it has a maximum stable set and that implies a maximal stable set in the finite case.

In the infinite case that doesn't work anymore because there can be maximum sets which are not maximal (because adding a vertex to an infinite set doesn't change the cardinality).

However, the graphs I can think of always admit a maximal stable set. I tried to use the extensionality property of the rado graph to get another result, but that works only with finite subset, so once I've taken the union over a monotone series of stable sets I can't get any result. I've also tried working with $mathbbR$ with $rsin E$ iff (or iff not) $r-sinmathbbQ$, but I could find maximal sets again (take a representative system of the equivalence relation (or take $mathbbQ$ in case of "iff not")). I'm at loss.

Hence the question: Does every graph have a maximal stable set? Please provide a proof or reference to one in your answer.

With the axiom of choice, yes. If $X$ is the set of stable subsets of $(G,E)$, then we want to prove that $(X,subseteq )$ has maximal elements. This is the case, because it is an inductive partial order. In fact, let $mathscr Csubseteq X$ be a totally ordered subset. Then, $bigcupmathscr C$ (the union of the elements of $mathscr C$) is an upper bound of $mathscr C$ in $(X,subseteq)$. In fact, we just need to prove that $mathscr C$ is stable. Let $u,vin bigcupmathscr C$. By definition, there are $Uinmathscr C$ and $Vinmathscr C$ such that $uin U$ and $vin V$. Since $(mathscr C,subseteq)$ is a total order, we do not lose generality by assuming that $Usubseteq V$, and therefore that $uin V$ as well. Since by hypothesis $V$ is stable and $u,vin V$, $uvnotin E$.

By Zorn's lemma, $X$ has maximal elements, QED.

Added: Viceversa, if every graph has a maximal stable set, let $X$ be a set and $mathscr P$ be a partition of $X$. Let $G=X$ and define the adjacency relation $$uvin Eiff (une vland exists Pinmathscr P, uin Pland vin P).$$

A maximal stable set of $(G,E)$ is precisely what the axiom of choice demands.