On Partitioning the Edges of Graphs into Connected Subgraphs

NEW

Problem: Reconstructed statement: for a finite graph $G$ and integer $s\ge1$, an $s$-partition is a partition of $E(G)$ into parts of size $s$, except possibly one “small” part of size $<s$. The revised question asks whether there is a finite integer $c(s)$ such that every $c(s)$-edge-connected graph has such a partition with every size-$s$ part inducing a 2-edge-connected subgraph. If the intended question was a single connectivity bound working for all $s$, the answer below is stronger.

Result: No such finite degree of edge-connectivity exists, for any fixed $s\ge1$.

Proof. Fix $s\ge1$ and any proposed connectivity $c$. Choose a finite simple graph $G$ with girth $>s$ and edge-connectivity at least $c$. Such graphs exist: take a finite Cayley graph of a finite quotient of a free group in which no nontrivial reduced word of length at most $\max(s,2)$ vanishes; it has girth $>s$, and by the Mader–Watkins theorem a connected finite vertex-transitive $d$-regular graph has edge-connectivity $d$. Taking $d\ge c$ gives the desired $G$.

Now suppose $G$ had the revised $s$-partition. Since $G$ has more than $s$ edges, the partition contains at least one full part $F$ with $|F|=s$. If $G[F]$ were 2-edge-connected, then $G[F]$ would contain a cycle. That cycle would have length at most $|F|=s$, hence would also be a cycle of $G$, contradicting $\operatorname{girth}(G)>s$. Therefore no full part can be 2-edge-connected, so the required partition cannot exist.

Thus arbitrarily highly edge-connected graphs fail the revised requirement. The obstruction is not a small $s=1,2$ degeneracy; it holds for every $s$.

Citation: M. Jünger, G. Reinelt, and W. R. Pulleyblank, “On partitioning the edges of graphs into connected subgraphs,” Journal of Graph Theory 9 (1985), 539–549. Standard ingredients used above: residual finiteness of free groups, and Mader’s theorem that finite connected vertex-transitive graphs are maximally edge-connected.