0
$\begingroup$

Does a graph with infinite nodes that is not fully connected have a countably infinite or a uncountably infinite number of paths originating from a single node?

We are only concerned with paths that do not contain loops. Also, we can assume that each node has between one path to the maximum possible number of unique, non looping paths to each other node.

$\endgroup$
  • 2
    $\begingroup$ I depend of your graph. If you have an infinite binary tree, then the number of path originating from the origin is uncountable, but if your graph has another geometry, it can have a countable number of path originating from one node (take a chain) $\endgroup$ – Tryss Apr 17 '15 at 20:30
  • $\begingroup$ Can you outline or link to a proof that an infinite node binary tree has an uncountably infinite number of paths originating from the origin? $\endgroup$ – noesis23 Apr 17 '15 at 20:56
  • $\begingroup$ Actually, I made an assumption and considered that infinite path could be considered as a path... it's not true if you consider only the path of finite lenght $\endgroup$ – Tryss Apr 17 '15 at 20:59
0
$\begingroup$

If I take a graph with vertex set $\mathbb{R}$, and connect 0 to every $x \in \mathbb{R} \setminus \{ 0 \}$, then I have uncountably many finite paths from 0.

If on the other hand you require the vertex set to be countable, then the number of finite paths from any given point is countable. (As it is a countable union of countable sets).

As Tryss says, if you allow paths to be infinite in length, then the cardinality of paths extending from a point is heavily dependent on geometry.

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