On the Decomposition of a 3-Connected Graph into Cyclically 4-Edge-Connected Components

Аннотация

A graph is called cyclically 4-edge-connected if removing any three edges from it results in a graph in which at most one connected component contains a cycle. A 3-connected graph is 4-edge-connected if and only if removing any three edges from it results in either a connected graph or a graph with exactly two connected components one of which is a single-vertex one. We show how to associate with any 3-connected graph a tree of components such that every component is a 3-connected and cyclically 4-edge-connected graph.