Let $X$ be an infinite set and consider the undirected clique graph $Q(X)$. That is, $Q(X)$ has an edge between $x$ and $x'$ in $X$ for every distinct $x$ and $x'$.
My question is this:
In what circumstances can we orient the edges in $Q(X)$, such that each $x$ has only finitely many outgoing edges (and thus necessarily infinitely many incoming edges).
We can rephrase the question as a graph colouring question. Consider a set of colours $C$, having the same cardinality as $X$, and choose a fixed but arbitrary isomorphism $c: X\cong C$.
In what circumstances can we $C$-colour the edges in $Q(X)$ such that
- For each $c$, only finitely many edges have colour $c$.
- If an edge between $x$ and $x'$ has colour $c$ then $c=c(x)$ or $c=c(x')$.
Advice is welcome. Thank you.
You are asking, when does the complete graph on an infinite set $X$ admit an orientation in which every vertex has finite outdegree? The answer is that such an orientation exists if and only if $X$ is countable.
Suppose $X$ is countable. Without loss of generality, assume $X=\mathbb N$. Let the edge between vertices $x$ and $y$ be directed from $x$ to $y$ if and only if $x\gt y$. Plainly each vertex has finite outdegree.
Suppose $X$ is uncountable. Assume for a contradiction that the complete graph on $X$ is oriented so that each vertex has finite outdegree. Choose a countably infinite subset $S$ of $X$. Then the set $N^+[S]$ consisting of the vertices in $S$ and their outneighbors is also countable. Since $X$ is uncountable we can choose a vertex $x\in X\setminus N^+[S]$. Then every vertex is $S$ is an outneighbor of $x$, so $x$ has infinite outdegree, contradicting our assumption.
The latter argument assumes the axiom of choice. Without the axiom of choice, there can be an uncountable tournament (oriented complete graph) in which each vertex has finite outdegree. For instance, such a tournament exists if the axiom of choice for countably many $3$-element sets is false, while the axiom of choice for countably many $2$-element sets is true.