decomposing a graph in connected components

216 Views Asked by At

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, ...

1

There are 1 best solutions below

6
On

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$.