The subject of the paper is to propose a simple O(ℝVℝ+ℝEℝ) algorithm for finding all 3-edge-components of a given undirected multigraph G=(V,E). A 3-edge-connected component of G is defined as a maximal set of vertices such that G has at least three edge-disjoint paths between every pair of vertices in the set. The algorithm is based on the depth-first search (DFS) technique. For any fixed DFS-tree T of G, cutpairs of G are partitioned into two types: a type 1 pair consists of an edge of T and a back edge; a type 2 pair consists of two edges of T. All type 1 pairs can easily be determined in O(ℝVℝ+ℝEℝ) time. The point is that an edge set KE(T) in which any type 2 pair is included can be found in O(ℝVℝ+ℝEℝ) time. By adding certain edges to G, we can construct in O(ℝVℝ) time a graph G' such that all 3-edge-components of G appear as connected components after all edges contained in type 1 pairs or in the edge set KE(T) are deleted from G'.
