Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Does there exist a connected 2-regular uncountable graph? Can I use the axiom of choice to construct an uncountable path of elements from the reals?
The question arose when reading this:
Also, it is not hard to show that any connected, infinite, 2-regular graph is isomorphic to the integers (where each n is adjacent to n-1 and n+1), so unless you consider that a cycle (which you shouldn't), any attempt to build an infinite cycle is going to end poorly.
There is some sort of an issue with the notion of a path. Since it implies that the distance between any two nodes is finite. At least in the usual notion of path.
So until you supply a different notion, I will assume that this means just that. That the distance between two points on the path is finite.
Now suppose that $(V,E)$ is a graph such that each node has exactly two neighbors. Choose one node, $v_0$, and choose one neighbor $v_1$, and the other is now $v_{-1}$. Suppose that $v_n$ and $v_{-n}$ were defined with $v_{n-1}$ as a neighbor of $v_n$ and $v_{-(n-1)}$ a neighbor of $v_{-n}$, we define $v_{n+1}$ as the other neighbor of $v_n$ and similarly $v_{-(n+1)}$. This construct can go on indefinitely, or until we reach a full circle, and $v_n=v_k$ for some previously defined $k$ (one of which is necessarily negative).
Now suppose that the graph is connected and infinite, so the construction must go through all the integers, and therefore the graph is Dedekind-infinite ($k\mapsto v_k$ is an injection from $\Bbb Z$ into $V$). But since it's also connected, and if $v$ is connected to $v_0$ it is necessarily some $v_k$ for an integer $k$, then this enumeration of the vertices is in fact a bijection of the graph with $\Bbb N$. Note that we only made two choices here, so the axiom of choice wasn't used at any point.
On the other hand, it is possible to have a connected 3-regular graph which is uncountable, and in fact doesn't have any countably infinite subset. I claim that it is sufficient to show that a rooted tree whose root has two neighbors, and any other point has three can exist; in which case we can just take two copies of the tree and connect their roots to obtain such graph.
It is consistent that there is a family $\{A_n\mid n\in\Bbb N\}$ of sets of size $2$ which does not admit a choice function. Namely, there is no function $f(n)\in A_n$ for all $n$. Consider now the tree where on the $n$-th level there are functions with domain $\{0,\ldots, n-1\}$ with $f(i)\in A_i$ (these are finite choices, so they exist without appealing to the axiom of choice). And we order the tree by inclusion. Then each node has two successors (the possible two choices from $A_n$) and except the root, each node has a unique predecessor. So the proof is complete.
