Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen

Abstract

The main result states: Lete ₁,e ₂,e ₃ be three lines incident to the pointv (degv≥4) of the connected bridgeless graphG such thate ₁ ande ₃ belong to different blocks ifv is a cutpoint. “Split the pointv” in two ways: Lete ₁,e _j ,j=2, 3, be incident to a new pointv _1j and leave the remainder ofG unchanged, thus obtainingG _1j . Then at least one of the two graphsG ₁₂,G ₁₃ is connected and bridgeless. — A classical result ofFrink follows from this theorem which is the key to a simple proof of Petersen's theorem. Moreover, the above result can be used to prove practically all classical results on Eulerian graphs, including best upper and lower bounds for the number of Eulerian trails in a connected Eulerian graph. In the theory of Eulerian graphs, it can be viewed as the basis for good algorithms checking on several properties of this class of graphs.