Splitting Lemma for 2-Connected Graphs

Using a splitting operation and a splitting lemma for connected graphs, Fleischner characterized connected Eulerian graphs. In this paper, we obtain a splitting lemma for 2-connected graphs and characterize 2-connected Eulerian graphs. As a consequence, we characterize connected graphic Eulerian matroids. 1. Introduction Fleischner [1] introduced a splitting operation to characterize Eulerian graphs as follows. Let be a connected graph and with . If and are two edges incident with , then splitting away the pair of edges from the vertex results in a new graph obtained from by deleting the edges and , and adding a new vertex adjacent to and (see Figure 1). Figure 1 The following splitting lemma established by Fleischner [1] has been widely recognized as a useful tool in the graph theory. Splitting Lemma (see [1, page III-29]). Let be a connected bridgeless graph. Suppose such that and are the edges incident with . Form the graphs and by splitting away the pairs and , respectively, and assume and belong to different blocks if is a cut vertex of . Then either or is connected and bridgeless. This lemma is used to obtain the following characterization of Eulerian graphs. Theorem 1.2 (see [1, page V-6]). A graph has an Eulerian trail if and only if can be transformed into a cycle through repeated applications of the splitting procedure on vertices of a degree exceeding . Moreover, the number of Eulerian trails of equals the number of different labeled cycles into which can be transformed this way. Thus a connected graph is Eulerian if and only if there exists a sequence of connected graphs such that is a cycle and is obtained from by applying splitting operation once. The splitting operation may not preserve -connectedness of the graph. Consider the graph of Figure 2. It is -connected but the graph is not -connected for any two adjacent edges and . Figure 2 We obtain the splitting lemma for -connected graphs as follows. Theorem 1.3. Let be a -connected graph and let be a vertex of with . Then either is -connected for some pair of edges incident with or for any pair of edges incident with ; there is another pair of adjacent edges of such that is -connected. The next theorem is a consequence of the above result. Theorem 1.4. Let be a -connected graph. Then is Eulerian if and only if there exists a sequence of -connected graphs such that is a cycle and is obtained from by applying splitting operation once or twice for . A matroid is Eulerian if its ground set can be partitioned into disjoint circuits, and it is connected if any pair of its elements is contained