3
$\begingroup$

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.

|cite|improve this question|||||
$\endgroup$
  • $\begingroup$ What is an uncountable path? $\endgroup$ – William Sep 10 '14 at 7:39
  • 1
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 10 '14 at 7:55
  • $\begingroup$ @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. $\endgroup$ – Pål GD Sep 10 '14 at 8:03
  • 1
    $\begingroup$ 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. $\endgroup$ – William Sep 10 '14 at 8:18
  • 2
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila♦ Sep 10 '14 at 9:30
2
$\begingroup$

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.

|cite|improve this answer|||||
$\endgroup$

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.