Covering a bounded degree graph with subgraphs of bounded sizes

Question

Let $G$ be a connected graph on $n$ vertices with maximum degree $\Delta \ge 2$. Let $\mathcal G = \{G_1,G_2,\ldots\}$ be a collection of subgraphs of $G$ such that every edge of $G$ is contained in at least one $G_i$. Let $n_i$ be the number of vertices in $G_i$ and $n_{ij}$ be the number of vertices in $G_i \cap G_j$ for $i\ne j$.

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

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

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.

---

Attempt 1: The first condition is satisfied by the collection of all balls of radius $r \ge 1$, i.e, $\mathcal G = \{B(v,r): v\in V(G)\}$ where $B(v,r) = \{w\in V(G): d(v,w) \le r\}$ and $d$ is the edge-metric on $G$. Indeed, $|B(v,r)| \le \Delta^r$ for all $v$ because $G$ has maximum degree $\Delta$, so $N= \Delta^r$. However, it is not clear that the second condition is satisfied by this collection. The main culprits are balls that have very small intersections. I was wondering if we can cleverly remove some balls to avoid such small intersections, but I don't know how to do this.

Attempt 2: The second condition can be trivially satisfied by $\mathcal G = \{G\}$ but it doesn't satisfy the first condition. To make this a bit better, fix an $r\ge 1$, pick a vertex $v$, and consider the "shells" $G_i = B(v,(i+2)r-1) \setminus B(v,ir)$ for $i\in\{0,1,2,\ldots\}$. For sufficiently large $r$, one can see that $G_i \cap G_j \ne \emptyset$ iff $|i-j|\le 1$, and $n_{ij} \ge r$ for such $i,j$. Therefore, the second condition is satisfied. However, $n_{ij}$ can grow (perhaps exponentially) with $i$, so this collection still doesn't satisfy the first condition. Perhaps each shell can be further divided to satisfy both conditions, but I don't know how to do this.

---

Any help is much appreciated. Any references on relevant stuff are also welcome. Also, please feel free to add or edit the tags as I am not very familiar with this subject.

Answer 1

I think there is a simple solution to this. Let $r$ be sufficiently large and partition $V(G)$ (approximately) evenly into sets $V_1, V_2, \ldots, V_{n/r}$. Your $G_i$s will be the graphs induced on the $V_i$s as well as any nonempty bipartite graphs induced between $V_i$ and $V_j$ with $i\neq j$. Then every edge is covered (exactly once in fact). And any intersection between two $G_i$s is either of size $r$ or of size 0.

The number of nonempty bipartite graphs incident to $V_i$ is at most $r\Delta$. So $$\sum_{j\neq i\,:\,n_{ij}>0}\frac{1}{2^{n_{ij}/4\Delta}} \le r\Delta\cdot \frac{1}{2^{r/4\Delta}} $$ which is less than 1 if $r$ is large enough.