# Can we have an infinite tree in this graph?

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.

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.

• Thanks @Vladislav for your contribution (+1). Can you please explain what do you mean by "without going through other blue nodes"? Mar 14 '19 at 22:55
• = there is a path from b_i to a that doesn't contain blue nodes except b_i Mar 14 '19 at 22:56
• The thing is that it is possible to have $a\in V_6$ connected by a path to $b_4$ and $b_5$. Therefore $a\not\in G_4$ and $a\not\in G_5$. Thus, by deleting $G_i$'s you will not be deleting this particular $a$. Mar 14 '19 at 23:01
• I don' think I follow you. If, for instance, there is a path $a - a_x \in V_5 - b4$, it will be in $G_4$. If the only path from $a$ to $b_4$ is through $b_5$ it will be in $G_5$ (as $a$ is connected to $b_5$) Mar 14 '19 at 23:06
• Mar 14 '19 at 23:34

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.

• From the condition and the first picture you can deduce that $a_{n,i}$ can be adjacent to multiple nodes in $V_{n-1}$. Mar 15 '19 at 0:25
• How does it fail? The sets in partition don't have to be connected components of the graph. Mar 15 '19 at 0:30
• Your second "counterexample" does not contradict the claim. In your scenario where you have $b_4$ in the same connected component as $a_{4,1}$, that component will start in some $b_i$ for $i=1,2,3$. Thanks for the input though. Mar 15 '19 at 0:30
• Thanks for your comment. To quote: "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$". Note that in the counterexample, one connected component begins at $b_4$ and has vertices from $V_4$. Observe also that $4>4$ is a false statement. It's the $m>n$ condition that is crucial. Mar 15 '19 at 0:39
• If you make $V_4$ complete to $V_5$, does that connected component not include the single vertex in $V_1$? Mar 15 '19 at 1:09