# Splitting Lemma for 2-Connected Graphs

Authors: Y. M. Borse
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

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.


---

## Body

## 1. Introduction

Fleischner [1] introduced a splitting operation to characterize Eulerian graphs as follows. Let G be a connected graph and v∈V(G) with d(v)≥3. If x=vv1 and y=vv2 are two edges incident with v, then splitting away the pair {x,y} of edges from the vertex v results in a new graph Gx,y obtained from G by deleting the edges x and y, and adding a new vertex vx,y adjacent to v1 and v2 (see Figure 1).Figure 1The following splitting lemma established by Fleischner [1] has been widely recognized as a useful tool in the graph theory.Splitting Lemma
1.1 (see [1, page III-29]).LetGbe a connected bridgeless graph. Supposev∈V(G)such thatd(v)≥3andx,y,zare the edges incident withv. Form the graphsGx,yandGx,zby splitting away the pairs{x,y}and{x,z}, respectively, and assumexandzbelong to different blocks ifvis a cut vertex ofG.Then eitherGx,yorGx,zis connected and bridgeless.This lemma is used to obtain the following characterization of Eulerian graphs.Theorem 1.2 (see [1, page V-6]).
A graphG has an Eulerian trail T if and only if G can be transformed into a cycle C through repeated applications of the splitting procedure on vertices of a degree exceeding 2. Moreover, the number of Eulerian trails of G equals the number of different labeled cycles into which G can be transformed this way.Thus a connected graphG is Eulerian if and only if there exists a sequence G=G0<G1<⋯<Gn of connected graphs such that Gn is a cycle and Gi+1 is obtained from Gi by applying splitting operation once.The splitting operation may not preserve2-connectedness of the graph. Consider the graph G of Figure 2. It is 2-connected but the graph Gx,y is not 2-connected for any two adjacent edges x and y.Figure 2We obtain the splitting lemma for2-connected graphs as follows.Theorem 1.3.
LetG be a 2-connected graph and let v be a vertex of G with d(v)≥4. Then either Gx,y is 2-connected for some pair {x,y} of edges incident with v or for any pair {x1,y1} of edges incident with v; there is another pair {x2,y2} of adjacent edges of G such that (Gx1,y1)x2,y2 is 2-connected.The next theorem is a consequence of the above result.Theorem 1.4.
LetG be a 2-connected graph. Then G is Eulerian if and only if there exists a sequence of 2-connected graphs G=G0<G1<G2<⋯<Gn such that Gn is a cycle and Gi+1 is obtained from Gi by applying splitting operation once or twice for i=0,1,2,…,n-1.A matroidM is Eulerian if its ground set can be partitioned into disjoint circuits, and it is connected if any pair of its elements is contained in a circuit. It is clear that an Eulerian matroid may not be connected. A matroid is graphic if it is isomorphic to the cycle matroid of a graph. For matroid concepts and terminology, we refer to Oxley [2]. Raghunathan et al. [3] generalized the splitting operation of graphs to binary matroids and characterized Eulerian matroids in terms of this operation. We characterize connected Eulerian graphic matroids.In Section2, we prove Theorems 1.3 and 1.4. The matroid extension is considered in Section 3.


## 2. Eulerian 2-Connected Graphs

A block of a connected graphG is a pendant block if it contains exactly one cut vertex of G. For an edge e∈E(G), we denote the set of end vertices of e by V(e). For a vertex v of G, let EG(v) denote the set of edges of G which are incident with v, that is, EG(v)={e∈E(G)∣v∈V(e)}. Raghunathan et al. [3] characterized the circuits of the graph Gx,y in terms of circuits of G as follows.Lemma 2.1 (see [3]).
LetG be a graph and let {x,y} be a pair of adjacent edges of G. Then a subset C of edges of the graph Gx,y is a circuit in Gx,y if and only if C satisfies one of the following conditions:(i)
Cis a circuit in G containing x and y;(ii)
C is a circuit in G containing neither x nor y;(iii)
C=C1∪C2, where C1 and C2 are edge disjoint circuits of G with x∈C1, y∈C2, and C1∪C2 does not contain a circuit in G satisfying either (i) or (ii) above.Lemma 2.2.
LetG be a 2-connected graph and v be a vertex of G with d(v)≥3 and {x,y}⊆EG(v) such that the graph Gx,y is not 2-connected. Then Gx,y is connected and has exactly two pendant blocks. Further, one pendant block contains {x,y}, and the other pendant block contains EG(v)-{x,y}.Proof.
The proof is straightforward (see Figure3).Figure 3Lemma 2.3.
LetG be a 2-connected graph and let v be a vertex of G with d(v)≥4 such that Gx,y is not 2-connected for all {x,y}⊆EG(v). Then, for a given {x,y}⊆EG(v), the graph Gx,y is connected and has one cut vertex and two blocks.Proof.
Let{x,y} be a pair of edges incident with v. By Lemma 2.2, Gx,y is connected and has exactly two pendant blocks, say B1 and B2. We may assume that B1 contains {x,y} and B2 contains EG(v)-{x,y}. As d(v)≥4, we can choose two edges z, w from EG(v)-{x,y}. Let P1 and P2 be paths in Gx,y from v to vx,y with {x,z}⊂E(P1), {y,w}∩E(P1)=ϕ, {y,w}⊂E(P2) and {x,z}∩E(P2)=ϕ. Each of P1 and P2 corresponds to a cycle in G. By Lemma 2.1, these cycles are preserved in the graph Gy,w. Therefore Pi is contained in a block of Gy,w for i=1,2. By Lemma 2.2, Gy,w has two pendant blocks one containing edges y, w and the other containing EG(v)-{y,w}. Hence P1andP2 belong to different pendant blocks of Gy,w. Hence P1 and P2 share at most one vertex of Gy,w. However, P1 and P2 share all cut vertices of Gx,y. This implies that Gx,y has exactly one cut vertex. Therefore, by Lemma 2.2, Gx,y is connected and has exactly two blocks.Lemma 2.4.
LetG and v be as stated in Lemma 2.3. Then there exists a vertex u in G such that u is the cut vertex of Gx,y for all {x,y}⊆EG(v).Proof.
Let{x,y}⊆EG(v). By Lemma 2.3, Gx,y is connected and has one cut vertex, say u. Let {z,w}⊆EG(v). Then, by Lemma 2.3, Gz,w is also connected and has two blocks and one cut vertex. It suffices to prove that u is the cut vertex of Gz,w. If {x,y}={z,w}, then there is nothing to prove. Suppose {x,y}≠{z,w}. We may assume that x∉{z,w} and y≠w. By Lemma 2.3, Gx,w is connected and has two blocks, say B1 and B2. By Lemma 2.2, we may assume that B1 contains {x,w} and B2 contains EG(v)-{x,w}. Let e be an edge of G incident with v such that e∉{x,y,w}. Let P1 and P2 be paths in Gx,y from the vertex vx,y to v such that {x,w}⊂E(P1), {y,e}⊂E(P2), and {x,w}∩E(P2)=ϕ, {y,e}∩E(P1)=ϕ. Then each of P1 and P2 contains all cut vertices of Gx,y. Therefore u is a common vertex of P1 and P2. Further, each of P1 and P2 corresponds to a cycle in G. By Lemma 2.1, these cycles are preserved in the graph Gx,w and hence are contained in blocks of Gx,w. Therefore Bi contains Pi for i=1,2. Thus u is a common vertex of B1 and B2. This implies that u is a cut vertex of Gx,w. By Lemma 2.3, u is the only cut vertex of Gx,w. Let Q1 and Q2 be paths in Gx,w from v to vx,w such that {z,w}⊆E(Q1) and x∈E(Q2)-E(Q1). Then Qi contains the cut vertex u and, further, it corresponds to a cycle in G for i=1,2. By Lemma 2.1, Qi corresponds to a cycle of the graph Gz,w and hence is contained in a block of Gz,w for i=1,2. These cycles are contained in different blocks of Gz,w. By Lemma 2.2, one block of Gz,w contains the edges z, w and the other block contains the remaining edges of G that are incident with v. Hence Q1 and Q2 belong to different blocks of Gz,w. As u is a common vertex of Q1 and Q2, it is a cut vertex of Gz,w. Thus u is the cut vertex of Gz,w.Lemma 2.5.
LetG be a 2-connected graph and v be a vertex of G with the set of neighbours {v1,v2,…,vk}, where k≥4. Suppose Gx,y is not 2-connected for all {x,y}⊆EG(v). Then there exists a vertex u in G such that V(P)∩V(Q)={u} for any uvi-path P and uvj-path Q in G-v with i≠j.Proof.
By Lemma2.4, there exists a vertex u in G such that it is the cut vertex of Gx,y for all {x,y}⊆EG(v). Let P be a uvi-path and Q be a uvj-path in G-v with i≠j. We prove that V(P)∩V(Q)={u}. If P or Q is a trivial graph, then there is nothing to prove. Assume that |E(P)|≥1 and |E(Q)|≥1. Without loss of generality, we may assume that vi=v1 and vj=v2. Let e1=vv1 and e2=vv2. Then Ge1,e2 is connected and has two blocks, say B1 and B2 (see Figure 4). By Lemma 2.2, we may assume that B1 contains {e1,e2} and B2 contains EG(v)-{e1,e2}. Since u is the cut vertex of Ge1,e2, the paths P,Q are contained in B1. Let e3=vv3 and e4=vv4. Let P1 be a uv-path in B2 containing the edge e3 but avoiding e4. Let P2 be an uv-path in B2 containing e4 and avoiding e3. Then V(Pk)∩V(P)=V(Pk)∩V(Q)={u} for k=1,2. Let C1=P1∪P∪e1 and C2=P2∪Q∪e2. Then each of C1 and C2 corresponds to a cycle in G. Further, C1 contains e1, e3 and C2 contains e2, e4. Therefore, by Lemma 2.1, C1 and C2 correspond to cycles in Ge1,e3. By Lemmas 2.2 and 2.3, Ge1,e3 has exactly two blocks one of them contains C1 and the other contain C2. Hence C1 and C2 can share at most one vertex. This implies that P and Q can share at most one vertex. Thus V(P)∩V(Q)={u}.Figure 4Proof of Theorem1.3.
LetG be a 2-connected graph and let v be a vertex of G with d(v)≥4. Suppose Gx,y is not 2-connected for every pair {x,y} of edges incident with v. Let {v1,v2,…,vr} be the set of neighbours of v. Let x1 and y1 be any two edges of G incident with v. We may assume that x1=vv1 and y1=vv2. By Lemma 2.5, there exists a vertex u in G such that V(Pi)∩V(Pj)={u} for any i,j with i≠j, where Pi is a uvi-path and Pj is a uvj-path in G-v (see Figure 5). It is easy to see that d(u)≥d(v)≥4. If u=vi for some i, then Pi is the trivial graph containing only the vertex u. If v2=u, then set x2=y1=uv. If v3=u, then set y2=vu. In other cases, P2 and P3 are nontrivial graphs and hence we can take x2=uu2∈E(P2) and y2=uu3∈E(P3). It is easy to see that (Gx1,y1)x2,y2 is 2-connected.Figure 5Now, we prove Theorem1.4. Let dH(v) denotes the degree of a vertex v in a graph H.Proof of Theorem1.4.
LetG=G0 be an Eulerian 2-connected graph. Suppose G is not a cycle. Then G has a vertex v of a degree of at least 4. By Theorem 1.3, we get a pair {x1,y1} of edges incident with v such that either Gx1,y1 is 2-connected or (Gx1,y1)x2,y2 is 2-connected for some pair {x2,y2} of edges of G having a common vertex other than v. Denote this new 2-connected graph by G1. If G1=Gx1,y1, then dG1(v)=dG(v)-2 and dG1(w)=dG(w) for any w∈V(G)-{v}. If G1=(Gx1,y1)x2,y2, then dG1(v)=dG(v)-2, dG1(u)=dG(u)-2, and dG1(w)=dG(w) for any w∈V(G)-{u,v}, where u is the common vertex of x2 and y2 other than v. Further, the new vertices of G1 that are created in the splitting procedure have degree two. Obviously, G1 is Eulerian. If G1 is not a cycle, then we obtain a 2-connected Eulerian graph G2 from G1 by applying splitting operation once (or twice) which results in reducing the degree of a vertex (or two vertices) of G1 by 2. By repeating the same procedure and through a sequence of once or twice splitting operations performed in such a way that at each step the resulting graph is still 2-connected one finally arrives at a cycle which corresponds to an Eulerian trail of G. The converse is obvious.


## 3. Eulerian 2-Connected Matroids

In this section, we extend Theorem1.4 to connected Eulerian matroids. Raghunathan et al. [3] generalized the splitting operation of graphs to binary matroids and characterized Eulerian matroids in terms of this operation. In this section, we characterize connected Eulerian graphic matroids.Definition 3.1 (see [3]).
LetM=M[A] be a binary matroid and suppose x,y∈E(M). Let Ax,y be the matrix obtained from A by adjoining the row that is zero everywhere except for the entries of 1 in the columns labeled by x and y. The splitting matroid Mx,y is defined to be the vector matroid of the matrix Ax,y. The transition from M to Mx,y is called a splitting operation. The splitting operation for binary matroids is also studied in [3–6].We need the following three results.Lemma 3.2 (see [3]).
IfM(G) denotes the circuit matroid of a graph G, then for a pair {x,y} of adjacent edges in a graph G,M(Gx,y)=(M(G))x,y.Lemma 3.3 (see [3]).
LetM be a binary matroid and x,y∈E(M). Then M is Eulerian if and only if Mx,y is Eulerian.Theorem 3.4 (see [2, page 127).
LetG be a loopless graph without isolated vertices. If G has at least three vertices, then M(G) is a connected matroid if and only if G is a 2-connected graph.We obtain the following characterization of connected Eulerian graphic matroids.Theorem 3.5.
LetM be a connected graphic matroid. Then M is Eulerian if and only if it can be transformed into a circuit C through a sequence M=M0<M1<⋯<Mn=C of connected graphic matroids such that Mi+1 is obtained from Mi by applying splitting operation once or twice.Proof.
LetM be a connected graphic matroid. Then M is isomorphic to a cycle matroid M(G) of some graph G. In view of Theorem 3.4, we may assume that G is 2-connected. Suppose M is Eulerian. Then the graph G is Eulerian. By Theorem 1.4, there is a sequence of 2-connected graphs G=G0<G1<G2<⋯<Gn such that Gn is a cycle, and Gi+1 is obtained from Gi by applying splitting operation once or twice for i=0,1,2,…,n-1. Let Mi=M(Gi) for i=0,1,…,n. By Theorem 3.4, each Mi is connected. It follows from Lemma 3.2 that if Gi+1 is obtained from Gi by applying splitting operation once or twice then Mi+1 is obtained from Mi by applying splitting operation once or twice, respectively. Further, by Lemma 3.3, Mi is Eulerian for i=1,2,…,n.
Conversely, suppose there exists a sequence of connected graphic matroidsM=M0<M1<⋯<Mn=C, where Mi+1 is obtained from Mi by applying splitting operation once or twice for i=0,1,2,…,n-1. Since Mn=C is Eulerian, by Lemma 3.3, Mn-1 is Eulerian. By repeated applications of Lemma 3.3, we see that Mi is Eulerian for each i. Thus M=M0 is Eulerian.



---

*Source: 850538-2012-11-25.xml*