(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\subseteq\binom{V}{2}$ being a subset of the set of unordered pairs of $V$. For vertices $v,w\in V$ we write $vw:=\{v,w\}\in E$ and say $v$ and $w$ are adjacent.
A subset $S$ of $V$ is called stable iff for any $v,w\in S$ we have $vw\notin 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 $v\in V\setminus S$ holds that $S\cup\{v\}$ 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 $\mathbb{R}$ with $rs\in E$ iff (or iff not) $r-s\in\mathbb{Q}$, but I could find maximal sets again (take a representative system of the equivalence relation (or take $\mathbb{Q}$ 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.
Best 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 C\subseteq X$ be a totally ordered subset. Then, $\bigcup\mathscr 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,v\in \bigcup\mathscr C$. By definition, there are $U\in\mathscr C$ and $V\in\mathscr C$ such that $u\in U$ and $v\in V$. Since $(\mathscr C,\subseteq)$ is a total order, we do not lose generality by assuming that $U\subseteq V$, and therefore that $u\in V$ as well. Since by hypothesis $V$ is stable and $u,v\in V$, $uv\notin 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 $$uv\in E\iff (u\ne v\land \exists P\in\mathscr P, u\in P\land v\in P).$$
A maximal stable set of $(G,E)$ is precisely what the axiom of choice demands.