2
$\begingroup$

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.

enter image description here

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:

enter image description here

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks @Vladislav for your contribution (+1). Can you please explain what do you mean by "without going through other blue nodes"? $\endgroup$ – Chilote Mar 14 at 22:55
  • $\begingroup$ = there is a path from b_i to a that doesn't contain blue nodes except b_i $\endgroup$ – Vladislav Mar 14 at 22:56
  • $\begingroup$ 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$. $\endgroup$ – Chilote Mar 14 at 23:01
  • $\begingroup$ 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$) $\endgroup$ – Vladislav Mar 14 at 23:06
  • $\begingroup$ First case illustration Second case illustration $\endgroup$ – Vladislav Mar 14 at 23:34
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ From the condition and the first picture you can deduce that $a_{n,i}$ can be adjacent to multiple nodes in $V_{n-1}$. $\endgroup$ – Chilote Mar 15 at 0:25
  • 1
    $\begingroup$ How does it fail? The sets in partition don't have to be connected components of the graph. $\endgroup$ – Vladislav Mar 15 at 0:30
  • $\begingroup$ 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. $\endgroup$ – Chilote Mar 15 at 0:30
  • $\begingroup$ 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. $\endgroup$ – Joshua Schroeder Mar 15 at 0:39
  • $\begingroup$ If you make $V_4$ complete to $V_5$, does that connected component not include the single vertex in $V_1$? $\endgroup$ – Santana Afton Mar 15 at 1:09

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.