1 Introduction
Graphs considered in this note are finite and simple. Let G=(V,E) be a graph (undirected or directed). A subset X of V (resp. E) is called a feedback vertex (resp. edge) set if X intersects every cycle in G. (As usual, by a cycle in a directed graph we mean a directed one.) Let τ(G) (resp. τ′(G)) be the minimum size of a feedback vertex (resp. edge) set of G, and let ν(G) (resp. ν′(G)) be the maximum number of vertex-disjoint (resp. edge-disjoint) cycles in G. Clearly, ν(G)≤τ(G) and ν′(G)≤τ′(G); these inequalities, however, need not hold equalities in general. Thus a natural question to ask is: How large can τ(G)/ν(G) and τ′(G)/ν′(G) be? As shown by Erdős and Pósa (1965), for any undirected graph G, we have τ(G)=O(ν(G)logν(G)) and this bound is sharp; Erdős and Pósa (1962) also established essentially the same result for τ′(G) and ν′(G). The directed case is not so tractable, and good estimates of the corresponding ratios have yet to be found. Nevertheless, there exists a Ramsey type function f(t)>0 such that τ(G)≤f(ν(G)) for any directed graph G (the same result holds for τ′(G) and ν′(G) as well), as conjectured by Younger (1973) and confirmed by Reed et al. (1996).
Given these large ratios, the problems restricted to some important special graph classes, in particular, plane graphs, have also attracted much research effort. For a plane digraph G, Reed and Shepherd (1996) showed that τ(G)≤63ν(G). Interestingly, by the Lucchesi-Younger theorem (Lucchesi and Younger 1978), the equality τ′(G)=ν′(G) always holds. For the undirected case, Kloks et al. (2002) established that τ(G)≤5ν(G); they further proposed the following conjecture.
Advertisement
It is worthwhile pointing out that the bound in this conjecture, if correct, would be best possible: For any positive integer k, let H
i
be a copy of K
4 (the complete graph on four vertices) with vertex set {v
i,1,v
i,2,v
i,3,v
i,4} for 1≤i≤k, and let G be obtained from the disjoint union of H
1,H
2,…,H
k
by adding k−1 edges v
i,4
v
i+1,1 for 1≤i≤k−1. Then τ(G)=2k and ν(G)=k.
One purpose of this note is to prove the following theorem.
Advertisement
Theorem 1
For any plane graph
G, τ(G)≤3ν(G).
We shall also establish the following result for the edge version.
Theorem 2
For any plane graph
G, τ′(G)≤4ν′(G)−1. Furthermore, the constant 4 is best possible.
We remark that in the literature there are several other approximate min-max relations that are closely related to our work. For instance, Král and Voss (2004) studied the ratio between the minimum size of an odd cycle edge transversal and the maximum size of a collection of edge-disjoint odd cycles in a plane graph. They proved that the ratio is at most 2, which is best possible. For the corresponding vertex version, Fiorini et al. (2007) discovered that this ratio is at most 10, and conjectured that the best ratio is 2; they also gave a short proof of the aforementioned Král-Voss theorem.
The remainder of this note is organized as follows. In Sect. 2, we present a proof of Theorem 1 by using a discharging method, establish the upper bound in Theorem 2 based on the four-color theorem, and construct an infinite class of plane graphs to illustrate that the constant 4 in this bound is best possible. In Sect. 3, we exhibit a connectivity property enjoyed by a minimal counterexample to the above Kloks-Lee-Liu conjecture. In Sect. 4, we conclude this note by some remarks.
2 Proofs
Given a plane graph G, we use d(v) to denote the degree of a vertex v in G, use δ(G) to denote the minimum degree of G, and use d(f) to denote the degree of a face f in G (see Bondy and Murty 2008 for the definition). A face f of G is called a k-face if d(f)=k. A triangle in G is a cycle of length three.
As stated before, we shall prove Theorem 1 by using a discharging method, which relies heavily on the following structural description.
Lemma 1
Let
G=(V,E) be a 2-edge-connected triangle-free plane graph with
δ(G)≥3. Then one of the following two cases occurs:
(i)
Some 4-face of
G
contains at least one vertex with degree 3;
(ii)
Some 5-face of
G
contains at least 4 vertices with degree 3.
Proof
Let F be the set of all faces of G, and let w be the initial charge function defined as w(x)=3d(x)−12 for each x∈V∪F. By Euler’s Formula, we have
Now let w
∗ be the new charge function obtained from w by using the discharging rule:
$$\sum_{v\in V} w(v)+\sum_{f\in F} w(f)=12 \bigl(|E|-|V|-|F|\bigr)=-24.$$
(R)
for each vertex v with d(v)=3, v gets charge 1 from each of its adjacent faces.
Observe that Since
G contains a 4- or 5-face f
0 such that w
∗(f
0)<0.
-
w ∗(v)=0 for each vertex v with d(v)=3 (because G is 2-edge-connected);
-
w ∗(v)=w(v)=3d(v)−12≥0 for each vertex v with d(v)≥4; and
-
w ∗(f)≥w(f)−d(f)=2d(f)−12≥0 for each face f with d(f)≥6.
$$\sum_{v\in V} w^*(v)+\sum_{f\in F} w^*(f)=\sum_{v\in V}w(v)+\sum_{f\in F} w(f)=-24<0,$$
If d(f
0)=4, then w(f
0)=0. Since w
∗(f
0)<0, rule (R) guarantees the existence of at least one vertex v on f
0 with d(v)=3. Thus f
0 is as described in (i).
If d(f
0)=5, then w(f
0)=3. Since w
∗(f
0)<0, by rule (R), there exist at least four vertices on f
0 with degree 3. Hence f
0 is as described in (ii). □
Now we are ready to establish the main results of this note.
Proof of Theorem 1
For convenience, we call a collection of vertex-disjoint cycles in G a cycle packing. To prove the theorem, we shall actually exhibit a feedback vertex set X and a cycle packing \(\mathcal{C}\) in G such that \(|X|\leq 3 |\mathcal{C}|\). To this end, we apply induction on |V(G)|.
Since such X and \(\mathcal{C}\) can be obtained trivially if |V(G)|≤3, we proceed to the induction step. Let us make some simple observations about G. We may assume that
(1) G is connected, for otherwise the existence of such X and \(\mathcal{C}\) follows instantly from the induction hypothesis on the components of G.
(2) G is 2-edge-connected. Suppose not, e is a cut edge of G. By (1), G−e contains precisely two components G
1 and G
2. We can thus deduce the statement from the induction hypotheses on G
1 and G
2.
It follows immediately from (2) that
(3) The boundary of each of 4- and 5-faces of G is a cycle.
(4) G is triangle-free. Suppose the contrary: T=abca is a triangle in G. Let G′=G−{a,b,c}. Then the induction hypothesis guarantees the existence of a feedback vertex set X′ and a cycle packing \(\mathcal{C}'\) in G′ such that \(|X'|\leq 3 | \mathcal{C}'|\). Set X=X′∪{a,b,c} and \(\mathcal{C}=\mathcal{C}'\cup T\). Clearly, X is a feedback vertex set of G and \(\mathcal{C}\) is a cycle packing in G. As \(|X|=|X'|+3 \le 3 | \mathcal{C}'|+3=3|\mathcal{C}|\), we are done.
(5) δ(G)≥3. Otherwise, d(u)≤2 for some vertex u. Let v be a neighbor of u. By (2), we have d(v)≥d(u)=2. Let G′ be the graph obtained from G by contracting the edge uv. In view of (4), G′ contains no parallel edges. Thus, by the induction hypothesis, G′ has a feedback vertex set X′ and a cycle packing \(\mathcal{C}'\) such that \(|X'|\leq 3 | \mathcal{C}'|\). Let u′ be the vertex of G′ resulted from contracting edge uv, let D′ be the cycle containing v′ in \(\mathcal{C}'\), if any, and let D be the cycle in G obtained from D′ by expanding u′ into edge uv. Set X=X′ if u′∉X′ and X=(X′−{u′})∪{v} otherwise, and set \(\mathcal{C}=\mathcal{C}'\) if no cycle in \(\mathcal{C}'\) passes through u′ and \(\mathcal{C}=(\mathcal{C}'-\{D'\})\cup \{D\}\) otherwise. Clearly, X is a feedback vertex set of G and \(\mathcal{C}\) is a cycle packing in G. Since |X|=|X′| and \(|\mathcal{C}'|=|\mathcal{C}|\), these X and \(\mathcal{C}\) are as desired.
Combining (2), (4), and (5), we see that G is a 2-edge-connected triangle-free plane graph with δ(G)≥3. By Lemma 1, one of the following two cases occurs.
Case 1. Some 4-face f of G contains at least one vertex with degree 3.
Let C
f
=u
1
u
2
u
3
u
4
u
1 be the facial cycle of f (recall (3)) with d(u
1)=3, and let G′=G−{u
2,u
3,u
4}. By the induction hypothesis, G′ has a feedback vertex set X′ and a cycle packing \(\mathcal{C}'\) such that \(|X'|\leq 3 |\mathcal{C}'|\). Note that u
1 is contained in no cycle in \(\mathcal{C}'\) because its degree in G′ is 1. Set X=X′∪{u
2,u
3,u
4} and \(\mathcal{C}=\mathcal{C}' \cup \{C_{f}\}\). Clearly, X is a feedback vertex set of G and \(\mathcal{C}\) is a cycle packing in G. Since \(|X|=|X'|+3 \le 3 | \mathcal{C}'|+3=3|\mathcal{C}|\), we are done.
Case 2. Some 5-face g of G contains at least 4 vertices with degree 3.
Let C
g
=v
1
v
2
v
3
v
4
v
5
v
1 be the facial cycle of g (recall (3)) with d(v
i
)=3 for i=1,2,3,4, and let G′=G−{v
2,v
4,v
5}. By the induction hypothesis, G′ has a feedback vertex set X′ and a cycle packing \(\mathcal{C}'\) such that \(|X'|\leq 3 |\mathcal{C}'|\). Note that neither v
1 nor v
3 is contained in any cycle in \(\mathcal{C}'\) because both of them have degree 1 in G′. Set X=X′∪{v
2,v
4,v
5} and \(\mathcal{C}=\mathcal{C}' \cup \{C_{g}\}\). Clearly, X is a feedback vertex set of G and \(\mathcal{C}\) is a cycle packing in G. Note that \(|X|=|X'|+3 \le 3 |\, \mathcal{C}'|+3=3|\, \mathcal{C}|\), so X and \(\mathcal{C}\) are as desired. □
Proof of Theorem 2
Clearly, we may assume that G=(V,E) is 2-connected. Thus the boundary of each face of G is a cycle.
Let X be a feedback edge set of G with minimum size. Then G−X is a spanning tree of G. So |E|−|X|=|V|−1. By Euler’s Formula, |F|=|E|−|V|+2, where F is the set of all faces of G. Hence τ′(G)=|X|=|F|−1.
Consider the dual graph G
∗ of G. By the 4-color theorem, G
∗ contains an independent set U with |U|≥|V(G
∗)|/4=|F|/4. Now let us view U as a collection of faces of G. Note that the faces in U are pairwise edge-disjoint because U is independent in G
∗. Let \(\mathcal{C}\) be the collection of facial cycles of G such that \(C \in \mathcal{C}\) if and only if C is the boundary of a face in U. Then cycles in \(\mathcal{C}\) are pairwise edge-disjoint. Since \(\nu'(G) \ge |\,\mathcal{C}|=|U|\ge |F|/4=(\tau'(G)+1)/4\), we have τ′(G)≤4ν′(G)−1.
It remains to prove that the constant 4 in the about bound is best possible; this observation and its proof as described below are due to Daniel Král.
Let k be a positive integer, let C
i
=v
i,1
v
i,2…v
i,8
v
i,1 be a cycle of length 8 for 1≤i≤k, and let G be a plane graph obtained from the disjoint union of C
1,C
2,…,C
k
by adding four edges v
i,1
v
i+1,1, v
i,3
v
i+1,3, v
i,5
v
i+1,5, v
i,7
v
i+1,7 between C
i
and C
i+1 for each odd
i with 1≤i≤k−1, and four edges v
i,2
v
i+1,2, v
i,4
v
i+1,4, v
i,6
v
i+1,6, v
i,8
v
i+1,8 for each even
i with 1≤i≤k−1. Clearly, |F|=4(k−1)+2=4k−2. So
(1) τ′(G)=|F|−1=4k−3.
We propose to show that
(2) ν′(G)=k.
Since C
1,C
2,…,C
k
are disjoint cycles in G, we have ν′(G)≥k. Let us now apply induction on k to establish the reverse direction
(3) ν′(G)≤k.
The statement holds trivially for k=1. So we proceed to the induction step. Let \(\mathcal{C}\) be a collection of edge-disjoint cycles in G with maximum size. Since the maximum degree of G is three, two cycles in G are edge-disjoint if and only if they are vertex-disjoint. It follows that
(4) cycles in \(\mathcal{C}\) are pairwise vertex-disjoint.
We may assume that
(5) \(C_{i} \notin \mathcal{C}\) for any i with 1≤i≤k.
Otherwise, let H be the graph obtained from G by deleting all vertices on C
i
. In view of (4), all cycles in \(\mathcal{C}-\{C_{i}\}\) are contained in H. By induction hypothesis, ν′(H)≤k−1. So \(|\mathcal{C}|-1 \le k-1\). Thus \(\nu'(G)=|\mathcal{C}|\le k\) and hence (3) follows.
For convenience, let E
i
be the set of four edges between C
i
and C
i+1. As E
i
is an edge cut of G, we have
(6) each cycle in G contains an even number of edges in E
i
.
(7) For i=1,2,…,k−1, at least one edge in E
i
is outside all cycles in \(\mathcal{C}\).
Suppose on the contrary that edges in E
i
are all contained in cycles in \(\mathcal{C}\); let \(\mathcal{D}\) be the set of all cycles in \(\mathcal{C}\) that contain edges in E
i
. From the structure of G, it is easy to see that cycles in \(\mathcal{C}-\mathcal{D}\) are all vertex-disjoint from C
i
∪C
i+1, and hence all contained in G−V(C
i
∪C
i+1), which is denoted by H. By (6), \(|\mathcal{D}| \le 2\) because |E
i
|=4. Thus the maximality on \(|\mathcal{C}|\) allows us to assume that \(\mathcal{D}\) contains precisely two vertex-disjoint cycles of length six in the subgraph of G induced by all vertices in C
1∪C
2. By induction hypothesis, ν′(H)≤k−2. So \(|\mathcal{C}|-2 \le k-2\). Thus \(\nu'(G)=|\mathcal{C}|\le k\) and hence (3) follows.
By (5), each cycle in \(\mathcal{C}\) contains edges in some E
i
. By (6) and (7), there is at most one cycle in \(\mathcal{C}\) that contains edges in E
i
for 1≤i≤k−1. Combining these two observations, we conclude that \(|\mathcal{C}| \le k-1\). Therefore (3) and hence (2) is established.
Since k is an arbitrary positive integer, from (1) and (2) we deduce that the constant 4 in our bound is best possible. □
3 Connectivity
To tackle the Kloks-Lee-Liu conjecture, we have to first lift the minimum degree and connectivity of G so that this graph can be manipulated in a better way. The following lemma will surely serve as an important step in the proof of this conjecture, if any.
Lemma 2
Let
G
be a counterexample to the Kloks-Lee-Liu conjecture with minimum number of vertices. Then
G
is 3-connected.
Proof
Obviously, G is connected because it is a minimal counterexample to Conjecture 1.
Let us prove that G is 2-connected. Suppose not, u is a cut vertex of G. Let (G
1,G
2) be a 1-separator of G with V(G
1)∩V(G
2)={u}. If G
1 or G
2 has a maximum cycle packing which contains no cycle passing through u, then ν(G)=ν(G
1)+ν(G
2). By the minimality assumption on G, we have τ(G
i
)≤2ν(G
i
) for i=1,2. Thus τ(G)≤τ(G
1)+τ(G
2)≤2(ν(G
1)+ν(G
2))=2ν(G), a contradiction.
So we may assume that each maximum cycle packing of G
i
contains a cycle passing through u for i=1,2. Thus ν(G
i
−u)=ν(G
i
)−1 for i=1,2. By the minimality assumption on G, we obtain τ(G
i
−u)≤2ν(G
i
−u) for i=1,2. It follows that τ(G)≤τ(G
1−u)+τ(G
2−u)+1≤2(ν(G
1−u)+ν(G
2−u))+1=2(ν(G
1)+ν(G
2))−3<2(ν(G
1)+ν(G
2)−1)≤2ν(G), this contradiction implies that G is 2-connected.
To establish 3-connectivity, we assume the contrary: {a,b} is a 2-cut of G. Let (G
1,G
2) be a 2-separator of G with V(G
1)∩V(G
2)={a,b}. We break the remainder of the proof into a series of observations.
(1) ν(G−{a,b})=ν(G).
Otherwise, ν(G−{a,b})≤ν(G)−1. Let X be a minimum feedback vertex set of G−{a,b}. Then X∪{a,b} is a feedback vertex set of G. By the minimality assumption on G, we have |X|≤2ν(G−{a,b})≤2ν(G)−2. Thus τ(G)≤|X∪{a,b}|≤2ν(G), this contradiction yields (1).
(2) ν(G
1)+ν(G
2)=ν(G).
By (1), ν(G)=ν(G−{a,b})=ν(G
1−{a,b})+ν(G
2−{a,b}). So ν(G)≤ν(G
1−{a,b})+ν(G
2). On the other hand, it is clear that ν(G)≥ν(G
1−{a,b})+ν(G
2). Hence ν(G)=ν(G
1−{a,b})+ν(G
2), which implies that ν(G
2)=ν(G
2−{a,b}). Likewise, ν(G
1)=ν(G
1−{a,b}). Thus ν(G
1)+ν(G
2)=ν(G). So (2) holds.
(3) ab∉E(G).
Assume the contrary: a and b are adjacent in G. Let X
i
be a minimum feedback vertex set of G
i
for i=1,2. By the minimality assumption on G, we obtain |X
i
|≤2ν(G
i
) for i=1,2. As ab∈E(G), it can be seen that X
1∪X
2 is a feedback vertex set of G. Thus, using (2), τ(G)≤|X
1∪X
2|≤|X
1|+|X
2|≤2(ν(G
1)+ν(G
2))=2ν(G), a contradiction. So (3) is justified.
(4) ν(G
i
+ab)=ν(G
i
) for i=1 or 2.
Otherwise, ν(G
i
+ab)=ν(G
i
)+1 for i=1,2. Let \(\mathcal{C}_{i}\) be a maximum cycle packing of G
i
+ab for i=1,2. Then ab is contained in a cycle C
i
from \(\mathcal{C}_{i}\) for i=1,2. Set \(\mathcal{D}=(\mathcal{C}_{1} \cup \mathcal{C}_{2}- \{C_{1},C_{2}\}) \cup \{(C_{1}-ab)\cup (C_{2}-ab)\}\). Obviously, \(\mathcal{D}\) is a cycle packing in G. By (2), we thus have \(\nu(G_{1})+\nu(G_{2})+1=\nu(G_{1}+ab)+\nu(G_{2}+ab)-1=|\mathcal{C}_{1}|+| \mathcal{C}_{2}|-1=|\mathcal{D}|\leq \nu(G)= \nu(G_{1})+\nu(G_{2})\), again a contradiction. This proves (4).
Symmetry and (4) allow us to assume that ν(G
1+ab)=ν(G
1). Let X
1 be a minimum feedback vertex set of G
1+ab, and let X
2 be a minimum feedback vertex set of G
2. Since a and b are adjacent in G
1+ab, it is a routine matter to check that X
1∪X
2 is a feedback vertex set of G (in fact every cycle crossing a and b in G intersects X
1). By (2), τ(G)≤|X
1∪X
2|≤|X
1|+|X
2|≤2ν(G
1+ab)+2ν(G
2)=2(ν(G
1)+ν(G
2))=2ν(G), this contradiction completes the proof of our lemma. □
4 Concluding remarks
In this note we have established two approximate min-max relations on packing and covering cycles in plane graphs. We remark that the assertion of Theorem 1 actually holds for any graph G that can be 2-cell embedded in the projective plane, torus, and Klein bottle. To justify this, we need to establish a counterpart of Lemma 1 for a graph G on these surfaces. It can be shown using a discharging method that if G is 2-cell embedded in the projective plane, then Lemma 1 remains true; if G is 2-cell embedded in the torus or the Klein bottle, then one of the following four cases occurs: The remainder of the proof goes along the same line as that of Theorem 1.
(i)
Some 4-face of G contains at least one vertex with degree 3;
(ii)
Some 5-face of G contains at least three vertices with degree 3;
(iii)
For some 6-face of G, each of its incident vertices is of degree 3;
(iv)
Each vertex of G is of degree 4 and each face of G is a 4-face. Moreover, G contains eight distinct vertices v
1,v
2,…,v
8 and three distinct faces f
1, f
2, f
3, such that d(v
i
)=4 for i=1,2,…,8, and that C
1=v
1
v
2
v
7
v
8
v
1, C
2=v
2
v
3
v
6
v
7
v
2, and C
3=v
3
v
4
v
5
v
6
v
3 are facial cycles of f
1, f
2, f
3, respectively.
Despite our effort, the Kloks-Lee-Liu conjecture remains unsolved. To demonstrate the difficulty of this type of problems, let us take a second look at the proof of Theorem 2: Is it possible to produce a proof without using the 4-color theorem (4CT)? Such a proof is very hard to obtain, if not impossible. In fact, a long-standing open problem in graph theory posed by Erdős is to find a 4CT-free proof of the statement: Every n-vertex plane graph contains an independent set of size at least n/4. We point out that the Král-Voss theorem stated in Sect. 1 resembles Theorem 2 in nature, whose proofs (Král and Voss 2004; Fiorini et al. 2007) also rely heavily on the 4CT. We conclude this note by another closely related, innocently looking, yet frustrating conjecture made by Albertson and Berman (1979): Every n-vertex plane graph has a feedback vertex set of size at most n/2.
Acknowledgement
The authors are indebted to Professor Daniel Král for discovering that the constant 4 in Theorem 2 is best possible and for allowing them to incorporate his proof into this note.
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Open AccessThis is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.