We have a graph $G$. The vertices of $G$ are a measurable subset of $\mathbb{R}^n$ for some $n$. The degree of each vertex is bounded by some absolute finite constant $K$.


Q1. Does $G$ have a maximal independent set? (This is a set of mutually non-adjacent vertices such that each vertex not in the set is adjacent to at least one vertex in the set.)


Q2. If the answer to Q1 is "yes", can we find a maximal independent set which is measurable?


As you can probably tell, my set theory is weak.



Measurable maximal independent set in infinite graph of bounded degree
A relevant statement is Proposition 4.2. in



> 
> **[KST1999]** A. S. Kechris, S. Solecki, S. Todorcevic, *Borel Chromatic Numbers*. Advances in Mathematics **141**, 1-44 (1999)
> 
> 
> 


In short, the proposition shows that if you settle for *Borel* sets instead of arbitrary measurable sets, then Q1 and even Q2 *seem*(problem) to admit of an affirmative answer, and then even in greater generality (only local countability, not *boundedness*, of the vertex degrees required).**(caution)**


In detail,



> 
> **Proposition 4.2** ([KST1999, p. 12]) If $X$ is a [standard Borel space](https://www.encyclopediaofmath.org/index.php/Standard_Borel_space), and if $R\subset X\times X$ is a symmetric irreflexive relation, and if
> 
> 
> **(range)** for each Borel set $Y\subseteq X$ the set$\quad$ $R(Y) := \{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (y,x)\in R\}$ is a Borel set, too, and
> 
> 
> **(chrom)** if the Borel chromatic number of $(X,R)$ is countable,
> 
> 
> then $X$ contains a maximal $R$-independent set, which moreover is Borel (and hence measurable).
> 
> 
> 


To prepare for a *conditional answer to your question*, one also should quote (many thanks to Francis Adams for pointing this out):



> 
> **Proposition 4.5** ([KST1999, p. 13]) If $X$ is a standard Borel space, and if $R\subset X\times X$ is an irreflexive relation (not necessarily symmetric), and if
> 
> 
> **(preimage)** for each Borel set $Y\subseteq X$, the set $R^{-1}(Y):=\{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (x,y)\in R\}$ is a Borel set, too, an
> 
> 
> **(degree)** (\*) each $x\in X$ has finite degree in the *un*directed graph obtained from $R$ by symmetrizing the relation,
> 
> 
> then the Borel chromatic number of $(X,R)$ is countable.
> 
> 
> 


Now to your question proper. Suppose $R$ is any irreflexive symmetric relation on, not only a measurable, but a *Borel* vertex-set. (This assumption is why this answer is only a conditional answer to your question; arbitrary measurable sets are not covered, and would not allow to conclude that the maximal independent set is measurable, as exemplified by Han's example at [2018-02-19 03:22:58Z](https://mathoverflow.net/q/293316)). Suppose that as in the OP, $R$ has bounded vertex-degree; then **(degree)** in Proposition 4.5 holds.


Since $R$ is symmetric, for any $Y\subseteq X$ we have $R(Y)=R^{-1}(Y)$.


Now we can conclude the following:



> 
> if we **could**(problem) show that under the hypotheses in the OP it follows that **(range)**(\* \*) is true,
> then first Proposition 4.5 would imply that **(chrom)** is true, whereupon **Proposition 4.2** then would imply that $X$ contains a maximal $R$-independent set, which moreover is Borel (and hence measurable), answering the OP's question affirmatively.
> 
> 
> 


${}$\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_


(\*) In stating the following condition, op. cit. strangely first passes to the *un*directed graph underlying $R$, but then goes on to speak of an "outdegree" (cf. op. cit. Proposition 4.5); I find this confusing and can't explain this. I take the "out-degree" to simply mean "degree", since after all one is speaking of an *un*directed graph here.


(\* \*) Because of $R(Y)=R^{-1}(Y)$, we have **(range)** $\leftrightarrow$ **(premimage)**.


**(caution)** An earlier version of this answer erroneously stated that one may then also conclude that the maximal independent set was *(topologically-) discrete*; this particular additional statement was **false**. (And quite nonsensical, since in Proposition 4.2 no topology is specified.) I was misled by the unusual usage of 'discrete' in op. cit. (and by my predjudices: I was thinking of the *Lebesgue* $\sigma$-algebra on $\mathbb{R}^d$, which makes one think of topology), but Propostion 4.2 in op. cit. is *more general* and does **not** use 'discrete' in the topological sense: unusually, 'discrete' in op. cit. is nothing but a synonym for what in graph-theory is called 'independent' (i.e., set no two members of which are connected by an edge). My error is understandable: in the setting of Borel-spaces, taking 'discrete' to have its usual topological meaning is quite reasonable, so why would one rummage through the article to find the definition of 'discrete'?


*However*, my statement that the maximal independent set could in addition be assumed to be discrete was not only not the intended one, but it is also materially **false**: a counterexample is the graph with vertex-set equal to the *unit-circle*, and two points adjacent if and only if one can be carried to the other by rotating the circle by a *rational* angle. (This is precisely the *complement* of the graph defined by Han at [2018-02-19 03:22:58Z](https://mathoverflow.net/q/293316).)


In this graph, the set $\{ (\cos(\varphi),\sin(\varphi))\colon\quad \varphi\in\mathbb{Q}\cap[0,2\pi)\}$ is a maximal independent set. Of course---being countable---it is Borel (as it must by Proposition 4.2.) but, needless to say, it is **not** (topologially-)discrete.


(problem) The problem is that, some helpful comments notwithstanding, I still don't see whether the following is true



> 
> **(problem)** For any standard Borel space $X$, any Borel set $Y\subseteq X$, and any irreflexive symmetric relation $R\subset X\times X$ with *finite* degree at each point, does it follow that he set $R(Y) = \{x\in X\colon\ \exists y\qquad y\in Y\quad\wedge\quad (y,x)\in R\}$ is a Borel set, too?
> 
> 
> 


I did not look long into this matter, but in view of some similar results depending on the topology, I would rather suspect that **(problem)** has *negative* answer. Some results I looked at involve images of Borel sets under finite-to-one *functions*, which seems somewhat related, but $R$ need not be a function, and moreover some of the relevant results make conditions on topologies, which one does not have available here at all.


