# Does there exist a connected 2-regular uncountable graph, or an uncountable path?

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.

• What is an uncountable path? Sep 10, 2014 at 7:39
• The Long Line might work here? You need axiom of choice to prove that an uncountable well-ordered set exists. I do have some doubts about whether the graph there is 2-regular. The ordinals that are not immediate successors may create problems. It's been decaded since I thought about the long line, so leaving this for a knowledgable person to decide. Sep 10, 2014 at 7:55
• @William The idea was that it was a path with uncountably many vertices. I want to avoid using any loaded words such as sequences etc., since they might be interpreted as by definition being countable. Sep 10, 2014 at 8:03
• The usual definition of path states that between any two vertices on a path, the path gives a finite walk. Note that a graph is not a transitive relation. I do not know of anyway to meaningfully define a path except as a sequence of successively connected points. Sep 10, 2014 at 8:18
• @Jyrki: You most certainly don't need the axiom of choice. You need the power set axiom. You do need the axiom of choice to prove that the long line has the cardinality of the continuum though. Sep 10, 2014 at 9:30

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