# Removable Cycles Avoiding Two Connected Subgraphs

Authors: Y. M. Borse; B. N. Waphare
Journal: ISRN Discrete Mathematics
 (2013)

---

## Abstract

We provide a sufficient condition for the existence of a cycleC in a connected graph G which is edge-disjoint from two connected subgraphs H1 and H2 of G such that G−E(C) is connected.


---

## Body

## 1. Introduction

Prompted by Hobbs' conjecture, Jackson [1] proved that if G is a 2-connected simple graph of minimum degree at least 4 and e∈E(G), then G-e contains a cycle C such that G-E(C) is 2-connected. Lemos and Oxley [2] generalized this result as follows.Theorem 1.
LetG be a 2-connected simple graph and let H be a subgraph of G such that H is either 2-connected or K2. Suppose that dG(v)≥4 for all v in V(G)-V(H) and G has a cycle that is edge-disjoint from H. Then there exists a cycle C in G that is edge-disjoint from H such that G-E(C) is 2-connected.Borse and Waphare [3] obtained the following result for the class of connected graphs which is analogous to the above theorem and is an improvement of a result due to Sinclair [4].Theorem 2.
LetG be a connected simple graph and let H be a connected subgraph of G such that there is a cycle in G that is edge-disjoint from H. Suppose that dG(v)≥3 for all v∈V(G)-V(H). Then there exists a cycle C in G that is edge-disjoint from H such that G-E(C) is connected.The problem of the existence of cycles in graphs deletion of whose edges preserve connectedness is well studied in the literature (see [1–10]). In this paper, we improve Theorem 2 as follows.Theorem 3.
LetG be a connected simple graph and let H1 and H2 be connected subgraphs of G. Suppose that there are at least two cycles in G-E(H1∪H2) and further, no two edges of G-E(H1∪H2) form an edge-cut of G. Then there exists a cycle C in G that is edge-disjoint from both H1 and H2 such that G-E(C) is connected.LetG be a connected graph of minimum degree at least three and let H1 and H2 be connected subgraphs of G. If G-E(H1∪H2) has only one cycle, say C, then G-E(C) is not connected if a subset of E(C) forms an edge-cut of G. Therefore, in Theorem 3, we must assume that G-E(H1∪H2) contains at least two cycles. The following example shows that the condition in Theorem 3 regarding an edge-cut of G is necessary. Let G1 and G2 be two disjoint copies of Kn with n≥4. Suppose that ei=uivi is an edge of Gi for i=1,2. Let Hi=Gi-ei for i=1,2. Let G be the graph obtained from H1 and H2 by adding two new vertices u, v and seven new edges u1u, uu2, u2v2, v2v, vv1, v1u1, and uv; see Figure 1. Then G is simple, connected and the minimum degree of G is 3. Let C1=u1u+uv+vv1+v1u1,  C2=uu2+u2v2+v2v+vu, and C3=u1u+uu2+u2v2+v2v+vv1+v1u1. Then C1,C2, and C3 are the only cycles of G-E(H1∪H2). For C∈{C1,C2,C3}, it is easy to see that G-E(C) is not connected as the set {uui,vvi} is a 2-edge-cut of G for each i∈{1,2}.Figure 1As a consequence of Theorem3, we get the following result.Corollary 4.
LetG be an Eulerian 3-edge-connected simple graph containing at least four mutually edge-disjoint cycles. Then there exist three mutually edge-disjoint cycles C1,C2, and C3 such that G-E(Ci) is connected for i=1,2,3.We refer to [11] for the terms that are not defined here.


## 2. Proof

In this section, we prove Theorem3 and its corollary. First we prove the following lemma.Lemma 5.
LetG,H1, and H2 be as in the hypothesis of Theorem 3. If there is an edge of G joining H1 and H2, then there exists a cycle C in G that is edge-disjoint from both H1 and H2 such that G-E(C) is connected.Proof.
Lete be an edge of G, having one end vertex in H1 and the other end vertex in H2. Let H′=H1∪H2∪e. Then H′ is a connected subgraph of G. Let C1 and C2 be cycles in G-E(H1∪H2). If C1 or C2 does not contain e, then it is a cycle in G-E(H′). If e belongs to both C1 and C2, then (C1∪C2)-e contains a cycle. Thus, in any case, there is a cycle in G-E(H′). Since G-X is connected for every subset X of edges of the graph G-E(H′) with |X|≤2,  dG(v)≥3 for all v∈V(G)-V(H′). Hence, by Theorem 2, there exists a cycle C in G-E(H′) such that G-E(C) is connected. Obviously, C is edge-disjoint from both H1 and H2.The number of edges of a cycle or a pathP is denoted by |P|. If x and y are distinct vertices of a cycle C of a graph G, then C[x,y] and C[y,x] denote the edge-disjoint paths along C which join x to y.Proof of Theorem3.
Suppose that the result is false and letG be a counterexample. Then there exist connected subgraphs H1 and H2 of G satisfying the hypothesis of the theorem such that for every cycle C in G that is edge-disjoint from H1∪H2, the graph G-E(C) is not connected. Choose H1 and H2 such that |E(H1∪H2)| is maximum. By a hypothesis, dG(v)≥3 for all v∈V(G)-V(H1∪H2). Therefore, by Theorem 2, H1∪H2 is not connected. Thus H1 is vertex disjoint from H2.
Claim 1. If C is a cycle in G-E(H1∪H2), then every component of G-E(C) contains H1 or H2.
LetC be a cycle in G-E(H1∪H2). Since Hi is connected, it is contained in a component Di of G-E(C) for i=1,2. If D1=D2; then, by Theorem 2, there exists a cycle Z in G-E(D1) such that G-E(Z) is connected, which is a contradiction. Therefore D1≠D2. We prove that D1 and D2 are the only components of G-E(C). Let A=V(C)-V(D1∪D2). It is sufficient to prove that A is an empty set. Assume that A is nonempty. Since G is connected, each component of G-E(C) contains a vertex of C. If a component of G-E(C) contains exactly one vertex of C, then the edges incident with that vertex form a 2-edge-cut of G, which is a contradiction. Hence each component of G-E(C) contains at least two vertices of C. Hence |A|≥2. Therefore there is a component D of G-E(C) different from D1 and D2 such that |V(D)∩A|≥2. Let x1,x2∈V(D)∩A. Let P be a path in D between two vertices of C. Then P∪C contains at least two cycles which are edge-disjoint with D1∪D2. By the maximality of |E(H1∪H2)|, we have D1=H1 and D2=H2. By Lemma 5, there is no edge between D1 and D2. Suppose that |A|=2. Then A={x1,x2}. It follows that G-E(C) has exactly three components and hence we get two edges e1,e2 of C, with each having one end in D1 and the other in D such that {e1,e2} is an edge-cut of G, a contradiction. Thus |A|≥3.
Letw∈V(C)∩V(D1). Then w∉A. By traversing from w along C on both sides, let v1∉V(D1) be the first vertex of C on one side and let v2∉V(D1) be the first vertex of C on the other side. By Lemma 5, v1,v2∉V(D2). We may assume that w∈V(C[v1,v2]). Then V(C[v2,v1])∩A=A. Let D1′=D1∪C[v1,v2]. Then D1′ is connected and |E(D1′∪D2)|>|E(H1∪H2)|. By the maximality of |E(H1∪H2)|,  G-E(D1′∪D2) contains at most one cycle. Let D3 be the component of G-E(C) containing v2. Then D3∉{D1,D2} and |V(D3)∩A|≥2. If |V(D3)∩A|≥3, then D3∪C[v2,v1] contains two cycles, which is a contradiction. Hence |V(D3)∩A|=2. This implies that there is a component D4 of G-E(C) such that D4∉{D1,D2,D3}. Traverse the path C[v2,v1] beginning at v2, let v2′≠v2 be the second vertex of D3 on this path. Let Pv2v2′ be a v2,v2′ path in D3. Let C1=Pv2v2′∪C[v2,v2′]. Then C1 is a cycle. If C[v2,v2′] does not meet D4, then C[v2′,v1] intersects D4 in at least two vertices giving a cycle which is disjoint from C1, a contradiction. Hence C[v2,v2′] contains a vertex x of D4. If this path contains another vertex y of D4, then C1∪Pxy contains two cycles, where Pxy is an x,y path in D4. This is a contradiction. Hence V(C[v2,v2′])∩V(D4)={x}. This implies that the path C[v2′,v1] meets D4 in a vertex z≠x. Let Pxz be an x,z path in D4. Then C1∪C[v2′,z]∪Pxz contains two cycles, which is a contradiction. This proves the claim.
Claim 2. If C1 and C2 are cycles in G-E(H1∪H2), then |V(C1)∩V(C2)|≥2.
Assume that the claim is false. LetC1 and C2 be cycles in G-E(H1∪H2) such that |V(C1)∩V(C2)|<2. Then C1 is edge-disjoint from C2. By Claim 1, each component of G-E(C1) contains H1 or H2. Thus G-E(C1) has exactly two components. We may assume that Hi is contained in a component Di of G-E(C1) for i=1,2. Obviously, C2 is contained in D1 or D2. We may assume that C2 is contained in D1. By the maximality of |E(H1∪H2)|, it follows that H2=D2. By Claim 1, G-E(C2) has only two components D1′ and D2′, with each containing H1 or H2. We may assume that Hi is contained in Di′ for i=1,2. Since H2∪C1 is connected, it is contained in D2′. Let Q be the set of all edges in G, having one end vertex in D1 and the other end vertex in D2. Then Q⊆E(C1). By a hypothesis, |Q|≥4. Let Q′ be the set of all edges in G, having one end vertex in D1′ and the other end vertex in D2′. Then Q′⊆E(C2) and |Q′|≥4.
IfD1-E(C2) is connected, then G-E(C2) is connected, a contradiction. Therefore we may assume that D1-E(C2) is disconnected. Obviously, D1′ is a component of D1-E(C2). Let S=V(G)-(V(D2)∪V(D1′)). Note that |V(C1)∩V(D1)|≥2,  |V(C1)∩V(D1′)|=0,  |V(C2)∩V(D2′)|≥2, and |V(C1)∩V(C2)|≤1. Hence |S|≥3. Let H=G[S]. Then H is vertex disjoint from both H1 and H2. If H contains a cycle C′ then C1∪C′ contains two cycles and hence we get two cycles in G-E(D2∪(D1′∪Q′)). By the maximality of |E(H1∪H2)|, we get a cycle C that is edge-disjoint from both H1 and H2 such that G-E(C) is connected, which is a contradiction. Thus H is a forest. Let H′=H-E(C1∪C2). Then H′ is a forest. Every edge e of G with one end vertex in S and the other end vertex in V(G)-S is either in Q or in Q′ and hence e∈E(C1) or e∈E(C2). As dG(v)≥3 for all v∈V(H′) and |V(C1)∩V(C2)|≤1, at most one vertex of H′ is isolated. Hence H′ contains an edge. Let T be a nontrivial tree in H′. Let v1 and v2 be two pendant vertices of T. Since dG(vi)≥3, vi∈V(C1)∪V(C2) for i=1,2. We may assume that v1∈V(C1). Suppose that |V(C1)∩V(T)|≥2. Let {x,y}⊆V(T)∩V(C1) and let P be the x,y path in T. Then C1∪P contains at least two cycles. These cycles are edge-disjoint from D1′∪Q′ and D2. Now, a contradiction follows from the maximality of |E(H1∪H2)|. Hence |V(T)∩V(C1)|≤1. Similarly, |V(T)∩V(C2)|≤1. This implies that V(Ci)∩V(T)={vi} for i=1,2. If T has a third pendant vertex v3, then v3 is in V(C1) or V(C2), which is a contradiction. Hence T has exactly two pendant vertices and therefore it is a path. As dG(v)≥3 for all v∈V(T),  V(T)⊆V(C1)∪V(C2). This implies that T has no internal vertex. Hence T is isomorphic to K2. Thus every component of H′ is isomorphic to either K1 or K2. Let e1=u1u2 be an edge of H′ with u1∈V(C1) and u2∈V(C2). Suppose that H′ has an another edge e2=u3u4. Then dH′(ui)=1 for each i∈{1,2,3,4}. We may assume that u3∈V(C1) and u4∈V(C2). Since Q′⊂E(C2), we may assume by suitable labeling that at least one edge of Q′ is not in C2[u2,u4]. It follows that the subgraph C1∪C2[u2,u4]∪e1∪e2 is edge-disjoint from the subgraph D2∪D1′∪G[Q′-E(C2[u2,u4])] and further, it contains at least two cycles. Obviously, D1′∪G[Q′-E(C2[u2,u4])] is connected and contains more edges than H1. A contradiction follows from the maximality of |E(H1∪H2)|. Hence H′ contains exactly one edge. Since V(H)=V(H′),  |V(H′)|≥3. As at most one vertex of H′ is isolated, |V(H)|=3. Let V(H)={u1,u2,u3}. We may assume that u1u2∈E(G),  u1∈V(C1),  u2∈V(C2), and u3∈V(C1)∩V(C2). Obviously, Q′-E(C2[u2,u3])≠ϕ or Q′-E(C2[u3,u2])≠ϕ. We may assume that Q′-E(C2[u2,u3])≠ϕ. The subgraph C2[u2,u3]∪u1u2∪C1 contains two cycles and further, it is edge-disjoint from the subgraphs D2 and D1′∪G[Q′-E(C2[u2,u3])]. A contradiction follows from the maximality of |E(H1∪H2)|. The proof of Claim 2 is completed.
By Claim 2, any two cycles inG-E(H1∪H2) has at least two vertices in common. This implies that there exist two vertices v1 and v2 and three mutually internally disjoint v1, v2 paths P1, P2, and P3 in G-E(H1∪H2). We may assume that |P1|≤|P2|≤|P3|. Let C1=P1+P2. Then C1 is a cycle in G-E(H1∪H2). By Claim 1, G-E(C1) has exactly two components each containing H1 or H2. Let Di be the component of G-E(C1) containing Hi for i=1,2. We may assume that the path P3 is contained in the component D1. Hence the vertices v1 and v2 are in D1. It follows from the maximality of |E(H1∪H2)| that D2=H2. Let Q be the set of all edges in G that have one end vertex in D1 and the other end vertex in D2. Then Q⊆E(C1). By a hypothesis, |Q|≥3. In fact, |Q|≥4. By Lemma 5, no edge of Q has an end vertex in H1 as H2=D2. Obviously, E(P1)∩Q≠ϕ or E(P2)∩Q≠ϕ. Let C′=P2+P3 if E(P1)∩Q≠ϕ; otherwise C′=P1+P3. Thus C′ is a cycle in G that is edge-disjoint from both H1 and H2 and further, E(P3)⊆E(C′) and E(P′)∩E(C′)=ϕ for some P′∈{P1,P2}. By Claim 1, G-E(C′) has exactly two components D1′ and D2′. We may assume that H1 is contained in D1′ and D2 is contained in D2′. As E(P′)∩Q≠ϕ,  D2∪P′ is connected and hence D2′ contains P′. So the vertices v1 and v2 do not belong to D1′. Thus D1-E(P3) has at least two components, one of which is D1′.
By a hypothesis,|V(D1′)∩V(C′)|≥2. Further, every component of D1-E(P3) contains at least one vertex of P3 and hence contains at least one vertex of C′. Suppose that there is a component F of D1-E(P3) containing two vertices x1 and x2 of C′ with F≠D1′. Let Px1x2 be an x1,x2 path in F. Obviously, Px1x2∪C′ contains at least two cycles. Thus there are at least two cycles in G-E(D1′∪(P′∪D2)). Further, E(H1∪H2)⊂E(D1′∪(P′∪D2)). Since D1′ and D2∪P′ are connected and are vertex disjoint subgraphs, by the maximality of |E(H1∪H2)|, there exists a cycle C in G that is edge-disjoint from D1′∪(P′∪D2) and hence edge-disjoint from H1∪H2 such that G-E(C) is connected, which is a contradiction. Thus C′ has exactly one vertex in common with every component of D1-E(P3) that is different from D1′. Since v1 and v2 are common vertices of D1-E(P3) and C′, there are two components F1 and F2 of D1-E(P3), both different from D1′ such that v1∈V(F1) and v2∈V(F2).
Suppose thatF1, F2, and D1′ are the only components of D1-E(P3). Let P′′∈{P1,P2}-{P′}. Then C′=P3+P′′. Suppose that P′′ does not meet D1′. Then, as P3 meets each of F1 and F2 only once, the corresponding two edges of P3 form a 2-edge-cut of G, which is a contradiction. Therefore P′′ meets D1′. Since P′′ is a v1,v2 path and |V(C′)∩V(Fi)|=1,V(P′′)∩V(Fi)={vi} for i=1,2. If P′′ meets D2, then D1′∪D2∪F1∪F2∪P′′=G-E(P3+P′) is connected, which is a contradiction as P3∪P′ is a cycle in G-E(H1∪H2). Thus P′′ does not meet D2. Hence Q∩P′′=ϕ. This shows that Q⊆E(P′). Traverse the path P′ beginning at v1 and suppose that P′ meets F2  at the first time in the vertex x. Let y be the last vertex of F1 on the v1,x subpath Pv1x of P′. Then the subpath Pxy of P′ contains at most two edges of Q. Extend the path Pxy to a v1,v2 path Pv1v2 by adding a y,v1 path in F1 and an x,v2 path in F2. Thus Q-E(Pv1v2)≠ϕ. As C′∪Pv1v2 contains at least two cycles, there are at least two cycles that are edge-disjoint from the connected subgraphs D1′ and D2∪G[Q-E(Pv1v2)] of G. Since H1 is contained in D1′,  H2 is contained in D2, and D2∪G[Q-E(Pv1v2)] is connected, by the maximality of |E(H1∪H2)|, there exists a cycle C that is edge-disjoint from D1′∪D2∪G[Q-E(Pv1v2)] such that G-E(C) is connected, which is a contradiction. Thus D1-E(P3) has at least four components.
SinceD1′ and D2′ are the only components of G-E(C′), the path P′ meets every component of D1-E(P3) except D1′. Also, |Q∩E(P′)|≥2. It follows that we can choose two components F1′ and F2′ of D1-E(P3) and two vertices x∈V(F1′)∩V(P′),  y∈V(F2′)∩V(P′) such that for the x,y subpath Pxy of P′ we have (E(P′)∩Q)-E(Pxy)≠ϕ. Let x′∈V(C′)∩V(F1′),y′∈V(C′)∩V(F2′) and let Pxx′ and Pyy′ be paths in F1′ and F2′, respectively, from x to x′ and y to y′. Then C′∪(Px′x+Pxy+Pyy′) contains at least two cycles and further, it is edge-disjoint from D1′,D2, and (E(P′)∩Q)-E(Pxy). Due to the maximality of |E(H1∪H2)|, there exists a cycle C that is edge-disjoint from both D1 and D2∪G[(E(P′)∩Q)-E(Pxy)] such that G-E(C) is connected, which is a contradiction. This completes the proof of the theorem.Proof of Corollary4.
LetZ1, Z2, Z3 and Z4 be mutually edge-disjoint cycles in G. By Theorem 3, there exists a cycle C1 in G-E(Z1∪Z2) such that G-E(C1) is connected. Since G is eulerian, every component of G-E(Z1∪Z2) is eulerian. Hence G-E(Z1∪Z2) has a cycle decomposition ℒ1 containing the cycle C1. Since Z3 and Z4 are edge-disjoint from Z1 and Z2,ℒ1 contains at least one cycle C1′ other than C1. As C1∪C1′ is edge-disjoint from Z1∪Z2, by Theorem 3, there exists a cycle C2 in G-E(C1∪C1′) such that G-E(C2) is connected. Obviously, each component of G-E(C1∪C2) is eulerian. Further, C1′ is a cycle in G-E(C1∪C2). There exists a cycle decomposition ℒ2 of G-E(C1∪C2) containing C1′. It is easy to see that G-E(C1∪C1′∪C2) contains at least one edge. Hence G-E(C1∪C2) contains at least one edge which is not in C1′. This implies that ℒ2 contains a cycle C2′ with C2′≠C1′. Hence, by Theorem 3, there exists a cycle C3 in G-E(C1∪C2) such that G-E(C3) is connected. Obviously, C1,  C2, and C3 are mutually edge-disjoint cycles.



---

*Source: 164535-2013-03-27.xml*