# Number of paths in a graph with infinite nodes

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.

• 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) – Tryss Apr 17 '15 at 20:30
• 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? – noesis23 Apr 17 '15 at 20:56
• 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 – Tryss Apr 17 '15 at 20:59

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.