Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity

Petersen's theorem, one of the earliest results in graph theory, states that any bridgeless cubic multigraph contains a perfect matching. While the original proof was neither constructive nor algorithmic, Biedl, Bose, Demaine, and Lubiw J. Algorithms 38 (1) showed how to implement a later constructive proof by Frink in O (n^4n) time using a fully dynamic 2-edge-connectivity structure. Then, Diks and Sta\'nczyk SOFSEM 2010 described a faster approach that only needs a fully dynamic connectivity structure and works in O (n^2n) time. Both algorithms, while reasonable simple, utilize non-trivial (2-edge-) connectivity structures. We show that this is not necessary, and in fact a structure for maintaining a dynamic tree, e. g. link-cut trees, suffices to obtain a simple O (n n) time algorithm.