Proving a graph has a property if all finite subgraphs have that property

Question

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if:

for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and $|U_i|\geq k$, for each $i\in I$ we can choose $v_i\in U_i$ such that $i\not=j \Rightarrow \{v_i ,v_j\} \notin E$.

Prove that if every finite subgraph of $G$ is $k$-good then $G$ is $k$-good.

---

I tried to handle it the same way that Erdős-de Bruijn Theorem (if every finite graph can be colored with 4 numbers such that... then every graph can be colored in 4 numbers such that...) was proven (the proof I am talking about is the one that uses the compactness theorem for propositional calculus) yet couldn't find a way to translate it to atomic proposition and describe the sets of propositions.

Answer 1

Note that it suffices to prove that every partition of $V$ into finite sets, $U_i$, with $|U_i|\geq k$ you can choose $v_i$ as described. The result would then hold for arbitrary partitions: if $U_i$ with $i\in I$ is a partition such that $|U_i|\geq k$ for all $i$, pick any subpartition of finite sets, $W_i$ indexed by $J$ such that $|W_i|\geq k$ for each $i\in J$, and find the requisite $v_i$ for each $W_i$. By choice, for each $U_j$ we can pick a unique $W_i$ that is a subset of $U_j$, and let $U_j$s representative be $W_i$s representative, $v_i$.

So, suppose that $U_i$, indexed by $i$, is a partition of finite sets such that $|U_i|\geq k$. For each finite $X\subseteq I$ let $f_X$ be a function where $f_X(U_i) \in U_i$ for every $i\in X$ such that $\{f_X(U_i), f_X(U_j)\}\not\in E$ whenever $i\not=j$. Such a function exists since the $\langle\bigcup_{i\in X} U_i, E\cap \bigcup_{i\in X} U_i\rangle$ is a finite subgraph and so is $k$-good.

Let $F$ be an ultrafilter containing each set $F_X=\{Y \subseteq I| X\subseteq Y$ and $Y$ finite$\}$ for each finite $X\subseteq I$.

Finally define $f(U_i)=x$ iff $\{X|f_X(U_i)=x\}\in F$. (This is well defined for otherwise the complement of $\{X|f_X(U_i)=x\}$, for each of at most finitely many different $x$, would belong to $F$. Since $F$ is an ultrafilter the intersection of these complements would belong to $F$, since there are at most finitely many things being intersected. But the intersection is empty and so cannot be a member of $F$.)

Suppose that $i\not= j$ and $f(U_i)=x$ and $f(U_j)=y$. This means that $\{X|f_X(U_i)=x\}$, $\{X|f_X(U_j)=y\}\in F$ and thus their intersection, $\{X|f_X(U_i)=x, f_X(U_j)=y\}$, is in $F$ and is therefore non-empty. So it follows that for some $X$, $f_X(U_i)=x, f_X(U_j)=y$, and by the way we chose each $f_X$, that $\{x,y\}\not\in E$.

Answer 2

Here is another way to prove it, this time using the propositional calculus. As before I shall show the result for partitions into finite sets and generalise as above. I'll just give the proof sketch, but it should be straightforward to fill in the details.

Let $U_i$ be a partition of $V$ into finite sets sets such that $|U_i|\geq k$ for each $i\in I$. Now define the following propositional theory. Create a set of labels as follows: $V\cup X$ where $X$ is a set of labels $\{v_i \mid i\in I\}$ chosen so that $V\cap X=\emptyset$.

For each $v_i\in X$, $u\in V$ there is a propositional letter $P_{v_i=u}$. And for each $u,v \in V\cup X$ another propositional letter $Q_{u,v}$ meaning "$u$ and $v$ are connected by an edge" (ideally we'd choose a notation which doesn't distinguish $Q_{u,v}$ from $Q_{v,u}$). Here is a propositional theory:

• $\bigvee_{u\in U_i} P_{v_i=u}$ for each $i \in I$.
• $P_{v_i=u}\rightarrow \neg P_{v_i=v}$ whenever $u\not=v$ and $u,v\in V$
• $Q_{v, u}$ if $\{v,u\}\in E$.
• $\neg Q_{v, u}$ if $\{v,u\}\not\in E$.
• $P_{v_i=u}\rightarrow (Q_{u, w}\leftrightarrow Q_{v_i,u})$ for any $u\in V$, $v_i\in X$ and $w\in V\cup X$.
• $Q_{u,v}\leftrightarrow Q_{v,u}$
• $\neg Q_{v_i,v_j}$ when $i\not=j$

By construction each finite subset is consistent, so there is a truth function, $t$, that satisfies the whole theory. Then simply define $f(U_i) = u$ if $t(P_{v_i=u})=1$.