Decomposition of a 2-Connected Graph into Three Connected Subgraphs

Аннотация

Let n₁+n₂+n₃ = n, and let G be a 2-connected graph on n vertices such that any 2-vertex cutset of G splits it into at most three parts. We prove that there exists a decomposition of the vertex set of G into three disjoint subsets V₁, V₂, V₃ such that |V_i| = n_i and the induced subgraph G(V_i) is connected for every i.