Vtyjkyuk

(Don't confuse this question with that one about maximal 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 maximum iff for any stable set $T$ of $G$ we have $|T|subseteq|S|$ ($|T|leq|S|$ in finite case) where $|A|$ denotes the cardinality of set $A$. If a maximum stable set of $G$ exists, we denote its cardinality by $alpha(G)$.

In the finite case every graph has a maximum stable set because the biggest possible cardinality for the maximum stable set is $|V|$ (archieved if the finite graph is without edges) and then we can find a maximum stable set from $S:Stext is stable setsubseteq 2^V$ because that set family is finite (from every finite set family we can find a set satisfying a property with that set having maximal cardinality).

I thought of an infinite example where this approach doesn't work anymore.

Let $G_0$ be the double ray, i.e. the countable 2-regular graph (you can get it from $mathbbZ$ when you connect the numbers with difference $1$). Note that $|V(G_0)|=alpha(G_0)=aleph_0$. The double ray constitutes the first "row" of our final graph. We get $G_1$ from $G_0$ by adding $aleph_1$ vertices to each of the vertices of $G_0$ (our first row), i.e. each of these clusters is connected only to a single vertex. Obviously, $|V(G_1)|=alpha(G_1)=aleph_1$. These $aleph_0$ clusters of $aleph_1$ vertices constitute our second row. We get $G_2$ from $G_1$ by adding $aleph_2$ vertices to each vertex of the second row and have $|V(G_2)|=alpha(G_2)=aleph_2$. And so on.

This way we get a graph sequence $G_0,G_1,G_2,ldots$ and can take their union $$G:=textstylebigcup_ninmathbbN_0G_n := (bigcup_ninmathbbN_0V(G_n), bigcup_ninmathbbN_0E(G_n))$$
which constitutes a proper graph with cardinality $|V(G)|=supaleph_n:ninmathbbN_0$, which is, to my knowledge, a proper cardinal. Now I can see that $alpha(G)=|V(G)|$ (probably), since I can take as a maximum stable set the vertices of each second row and $supaleph_2k:kinmathbbN_0=supaleph_n:ninmathbbN_0$. But I still don't know how to prove this in general.

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

No. Consider the vertex set
$$
V = (n, m) in mathbb N times mathbb N mid n geq m,
$$
and define an edge relation by
$$
E((n, m), (n', m')) iff n neq n'.
$$
Clearly, for each $k$, the set $(n, m) in V mid n = k$ is a stable set of cardinality $k + 1$. Furthermore, there can be no infinite stable set: if a node $(n, m)$ lies in the stable set, then all other nodes in the stable set must be of the form $(n, l)$, and there are only $n$ other such nodes. Thus the graph $(V, E)$ does not have a maximum stable set (in your sense).