Covering a connected bounded-degree bipartite graph with connected subgraphs

Question

Let $G = (L,R,E)$ be a finite connected bipartite graph with maximum degree $\Delta\ge2$. A subgraph $H$ is said to be left-neighbourhood closed (LNC for short) if every $v\in L(H)$ satisfies $\mathcal N_H(v) = \mathcal N_G(v)$, where $\mathcal N_G(v)$ is the set of vertices adjacent to $v$ in $G$. (This implies, in particular, that $H$ is an induced subgraph.)

Let $\mathcal G =\{ G_1,G_2,\ldots\}$ be a collection of connected LNC subgraphs of $G$ such that for every $v\in R$, the induced subgraph on the ball $B_G(v,2)$ is contained in some $G_i$. Let $n_i$ be the number of vertices in $R(G_i)$ and $n_{ij}$ be the number of vertices in $R(G_i \cap G_j)$ for $i\ne j$.

Question 1: For sufficiently large $n$ and fixed $\Delta$, is there a $\mathcal G$ such that,

1. for each $i$, $n_i \le N$ for some large $N = N(\Delta)>0$ independent of $i$ and $n$, and
2. for each $i$, $\sum_{j\ne i\,:\,n_{ij}>0}~\frac1{2^{n_{ij}/4\Delta}} \le \frac14$?

In other words, $G_i$ shouldn't be too large, and at the same time $G_i \cap G_j$ shouldn't be too small whenever it is non-empty.

---

Individually, these conditions are easy to satisfy. For instance, I can take $\mathcal G$ to be the collection of all balls of radius $r\ge 3$ around every vertex $v\in L$. It satisfies the first condition. The problem with this is that there might be balls which intersect in very few vertices, which will make it harder to satisfy the second condition. On the other hand, taking $\mathcal G = \{G\}$ satisfies the second condition trivially, but clearly not the first condition. So the question is if they can be satisfied simultaneously.

---

I have asked a related question before, but the answer to that one was straightforward. I originally thought it would also answer the question above, but it doesn't seem likely. Any thoughts/comments/hints/help is much appreciated.

Answer 1

I think the answer is yes when $G$ is a tree. (I am writing this as an answer instead of an update to the question because it does partially answer my question and also the question is too long already.)

For simplicity, let me consider a $\Delta$-regular tree (except for the leaves) of finite depth with a marked root $v \in R$. Consider the (connected induced) subtree of depth $2r-2$ rooted at $v$, for some positive even integer $r$ to be fixed later. Call it $G_1$. It contains $\sim\Delta^{2r-2}$ vertices. Moreover, it is easy to see that it is LNC.

Now, consider the set of vertices at depth $r$ from $v$. Note that all such vertices are in $R$. For every such vertex $u$, consider the rooted subtree "below" $u$. Repeat the above procedure for each such $u$.

Each $G_i$ built this way is a connected LNC subgraph of $G$ such that for every $w\in R$, $B_G(w,2)$ is contained in some $G_i$, provided $r$ is sufficiently large (and still independent of $n$ and $i$). Each $G_i$ contains $\sim \Delta^{2r-2}$ vertices, so the first condition is satisfied. Due to the choice of the depths of subtrees chosen to construct the $G_i$'s, each $G_i$ intersects with $\sim \Delta^r$ other $G_j$'s. And any such intersection contains $\sim \Delta^{r-2}$ vertices. Therefore, the second condition is also satisfied, provided $r$ is sufficiently large. This proves that the answer to my question is yes when $G$ is (almost) a $\Delta$-regular tree.

I think the above proof can be tweaked to make it work for any tree (not necessarily regular) with maximum degree $\Delta$.

When $G$ has cycles, I know some cases where the answer is yes. For instance, whenever $G$ is a "periodic" grid graph in any dimension, the answer is yes. Perhaps the above proof for a tree can be modified to make it work for $G$ with cycles but I don't yet know how. Any thoughts on this are much appreciated.