0
$\begingroup$

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

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

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – tomak
    Jan 14 '18 at 12:33
  • $\begingroup$ 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). $\endgroup$
    – ArsenBerk
    Jan 14 '18 at 12:38
  • $\begingroup$ Actually, I don't need such a result to prove what I actually want. $\endgroup$
    – tomak
    Jan 14 '18 at 12:54
  • $\begingroup$ 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. $\endgroup$
    – tomak
    Jan 14 '18 at 12:56
  • $\begingroup$ What you last said really makes sense. $\endgroup$
    – ArsenBerk
    Jan 14 '18 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.