3. Borel sets of graphs

problem

Show that the following sets are Borel in the space $"Graphs"$ of all graphs with vertex set $ℕ$ (identified with the Cantor space $C$ as discussed in class).

1. The set of all connected graphs.
2. The set of all trees.
3. The set of all bipartite graphs.
4. The set of all locally finite graphs (i.e., graphs where every vertex has finitely many neighbors).
5. The set of all $k$-colorable graphs for fixed $k∈ℕ$. (This is a bit trickier.)

1. Note that $G$ is connected if and only if for any vertex $x$ there exists a path joining $1$ and $x$: That is, there exists some finite list $v_1,…,v_n$ with $v₁=1$ and $vₙ=x$ so that for each $i∈\{1,…,n-1\}$, we have $\{vᵢ,vᵢ₊₁\}∈E(G)$.

   So we characterize connected graphs by the following boolean formula/circuit:

   $$\operatorname{connected}(G) = ⋀_{x∈ℕ} ⋁_{\substack{(v_1,…,v_n)∈ℕ^*\\v₁=1,\;vₙ=x}} \underbrace{ ⋀ᵢ₌₁ⁿ⁻¹ [\{vᵢ,vᵢ₊₁\}∈E(G)] }_\text{finite condition}.$$

   Notice that each conjunction/disjunction ranges over countable sets, so the circuit overall is finite.

2. Trees are defined as connected acyclic graphs. We characterized connectedness above; characterize acyclicity as follows: for any list of vertices $v_1,…,v_n$ with $n≥3$, these vertices do not form a cycle, i.e. there exist $i∈{1,…,n-1}$ such that $v_i v_{i+1}∉E(G)$.

   $$\operatorname{tree}(G) = \operatorname{connected}(G) ∧ ⋀_{\substack{n≥3\\(v₁,…,vₙ)∈ℕ^*}} ⋁ᵢ₌₁ⁿ [\{vᵢ,v_{(i+1)\bmod n}\}∈E(G)] .$$

3. Note that $G$ is bipartite if and only if it contains no odd cycles. Characterize this similarly as trees:

   $$\operatorname{bipartite}(G) = ⋀_{\substack{n≥3\\n≡1\bmod2\\(v₁,…,vₙ)∈ℕ^*}} ⋁ᵢ₌₁ⁿ [\{vᵢ,v_{(i+1)\bmod n}\} ∉ E(G)]$$
4. $$\operatorname{locallyFinite}(G) = ⋀_{v∈ℕ} ⋁_{N∈ℕ^*} ⋀_{u>N} [\{u,v\}∉E(G)].$$

   (Note $x⟺y$ can be implemented as $(x∧y)∨(¬x∧¬y)$, and $u∈{v_1,…,v_n}$ is just a finite disjunction $⋁_{i=1}^n (u=v_i)$.)

5. We rely on the following fact:

   theoremDeBruijn–Erdős

   If every finite subgraph of $G$ is $k$-colorable, then $G$ is $k$-colorable.