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.

  • $\begingroup$ Why is this tagged with propositional-calculus? $\endgroup$ – Joshua Taylor Jul 14 '14 at 20:41
  • $\begingroup$ it appeared in mathematical - logic final, and as I mentioned I expect the proof to be similar to the proof I am familiar with of Erdős-de Bruijn theorem which goes something like this: you describe a set of propositions that has a model if and only if G an be colored (4 colors etc...), and from the compactness theorem and the assumption that every finite subgraph of G can be colored you get that G can be colored. $\endgroup$ – Nathan Sikora Jul 15 '14 at 12:40
  • $\begingroup$ OK, the tag wiki for propositional-calculus says "Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with logic instead." I think you make a reasonable case. :) $\endgroup$ – Joshua Taylor Jul 15 '14 at 12:47

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$.


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$.

  • $\begingroup$ Ah, I just realised I misread the question as stipulating $|U_i|\leq k$ rather than $|U_i|\geq k$. The basic idea still works though; I've edited proof to accommodate. $\endgroup$ – Andrew Bacon Sep 7 '14 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.