# decomposing a graph in connected components

Obviously, a graph $G$ can be decomposed into its connected components.

Does this remain true for $2$-connectedness? I.e. can any graph be decomposed into $2$-connected components. And so forth and so on for $3$-connected, $4$-connected, $5$-connected, ...

• What is exactly is 2-connectednes
– Aqua
Jan 14 '18 at 12:14
• for every two vertices there exists at least two disjoint paths connecting them Jan 14 '18 at 12:16

A graph $G$ is $2$-connected if $|V(G)|>2$ and for every $x \in V(G)$ the graph $G − x$ is connected.
So, since you are asking it for any graph, the answer should be no. For example take $G$ as a tree. Since $G$ has no $2$-connected components, it cannot be decomposed into $2$-connected components as you suggested. And same example is valid for $k$-connectedness where $k \ge 2$.
• Actually, I want to prove that a graph is planar $\iff$ it has no minor $K_5$ or $K_{3,3}$. I have already shown it for a $3$-connected graph. And that is why I wanted to see if we could split any graph into $3$-connected components. Jan 14 '18 at 12:33
• Hmm, I see. So, should we take the question as "Can any $k$-connected graph be decomposed into $k$-connected components"? Because otherwise all trees are planar but we cannot prove it as in your method (although planarity is obvious for trees). Jan 14 '18 at 12:38
• If $G$ is planar. Either it is 3-connected, (I have my result) or it isn't. If it isn't, then either it has a $3$-connected component or not. If it does then we have our result. And if it doesn't, it cannot contain a $K_5$ or $K_{3,3}$ as a minor. Jan 14 '18 at 12:56