Can we have an infinite tree in this graph?

Question

Suppose that a graph has an infinite number of nodes set up as follows: let $V_n=\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}\cup\{b_n\}$ be a set of $n$ nodes. Let $V=\bigcup_{n=1}^\infty V_n$.

I am interested in graphs that can be built using nodes of V following the condition:

For every $n$, each $a\in\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}$ is connected to some $a'\in V_{n-1}$ by an edge.

Note: for every $n$, $b_n$ can be connected to some element(s) of $V_{n-1}$ but is not mandatory.

An example of such graph is depicted in the following picture where the elements $a_{n,1},a_{n,2},\dots,a_{n,n-1}$ are the white nodes and $b_n$ is the blue node.

I want to prove the following

Claim: There are only 2 types of graphs that can be built in this form: either a graph with an infinite connected sub-graph, or a graph that is union of disjoint finite connected sub-graphs that start at some $b_n$ and all the other nodes are in $V_m$ with $m>n$.

A graph of the 1st type is depicted in the picture above and a graph of the 2nd type is depicted in the picture below:

I think that the claim is true (almost trivially), but I don't know much about Graph Theory and maybe this claim can be proved very easily with some very well-know result in this area that I ignore. Any insight to prove this claim would be appreciated.

Answer 1

Suppose that $G$ has no infinite connected component.

On $i$th step let

$G_i = \{b_i\} \cup \{a|a$ is white vertex above, reacheable from $b_i$ without going through other blue nodes$\}$

then remove $G_i$ from G and continue.

Clearly $G_i$ is finite, has the only blue node and white nodes from above it, $\{G_i\}$ are disjoint.

To prove that $\{G_i\}$ is a partition required we only left to prove that every white node will be deleted. By induction we prove that after $i$th step every white vertex from $1..i+1$ levels has been deleted.

Let $a$ be an arbitrary white vertex from $(i+1)$th level. If $a$ was connected to another white from $i$th level it has been already deleted (as reachability is transitive). If it was not, it is connected to $b_i$ and will be deleted on $i$th step.

Answer 2

For each $a_{n,i}$, is it adjacent to exactly one edge in $V_{n-1}$, or can it be adjacent to multiple edges?

If only one edge, then the picture on top is incorrect, but I believe the statement is true. It can be observed that each $a_{n,m}$ has a neighbor beneath it, and so its component must continue downward until it necessarily terminates at $b_i$ for some $i$, the only place it could stop. If some element of $V_i$ were also in this connected component, there must be a vertex $a_{j,k}$ with two neighbors of a lower level, a contradiction. Then there either exists an infinite component, or not, and therefore it is one of the two cases.

[[ If multiple edges are allowed, then it is easy to come up with a counterexample; just take your second picture and make $V_5$ complete to $V_4$. Then, the condition fails since there is no infinite connected component, but $b_4$ would be in the same connected component as $a_{4,1}$. ]]

Edit: The bracketed argument does not work. I believe that by picking the $b_n$ such that $n$ is smallest in each connected component, this claim can be shown.

I hope this helps.