# 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

## 1 Answer

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.