PACKING AND COVERING TRIANGLES IN

TRIPARTITE GRAPHS

P.E. Haxell and Y. Kohayakawa

Abstract. It is shown that if G is a tripartite graph such that the maximum size of a set of pairwise edge-disjoint triangles is ν(G), then there is a set C of edges of G of size at most (2 − ε)ν(G) such that E(T) ∩ C ≠ ∅ for every triangle T of G, where ε > 0.044. This improves the previous bound of (7/3)ν(G) due to Tuza [6].

§0. Introduction

In this note we are concerned with a packing and covering problem for triangles in graphs. Let a graph G be given. We say that a family F of triangles in G is independent if the elements of F are pairwise edge-disjoint. Moreover, we say that a set C ⊂ E(G) of edges of G is a transversal of the set of triangles of G, or simply a transversal for G, if every triangle of G contains at least one element of C. We denote by ν(G) the maximum cardinality of an independent family of triangles in G, and by τ(G) the minimum cardinality of a transversal for G. It is clear that for every graph G we have ν(G) ≤ τ(G) ≤ 3ν(G). The graphs G = K^{4} and K^{5} show that we may have τ(G) as large as 2ν(G). In this note, we are concerned with an elegant conjecture of Tuza, first raised fifteen years ago [4], which states that τ(G) ≤ 2ν(G) for every graph G.

Some partial results on this conjecture have been obtained for certain special classes of graphs. In [6], Tuza shows that the conjecture is true for planar graphs, chordal graphs, and graphs with n vertices and at least 7n^{2}/16 edges. More recently, Krivelevich [3] has shown that graphs G without homeomorphic copies of K^{3,3} satisfy the conjecture, improving on Tuza’s result that the conjecture holds for planar graphs. Two fractional versions of the conjecture are considered by Krivelevich [3] as well. Tuza [6] also shows that for tripartite graphs G one has τ(G) ≤ 7ν(G)/3. In this note we prove that τ(G) ≤ (2−ε)ν(G) for tripartite graphs G, where ε > 0.044. We give a short, self-contained proof of the inequality τ(G) ≤ 2ν(G) (see Lemma 1); as we shall see, the difficulty will lie in getting the ε improvement. It is interesting to note that it has not even been proved that there is a constant c < 3 such that τ(G) < cν(G) for every graph G.

Our result is also a special case of a conjecture of Ryser on packing and covering in tripartite hypergraphs. A tripartite hypergraph H consists of three disjoint sets of vertices X_{1}, X_{2}, and X_{3}, and a set E of hyperedges E, where each hyperedge is

Typeset by AMS-TEX

1991 Mathematics Subject Classification. Primary 05C70, 05C35; Secondary 05D15.

Key words and phrases. Packing, covering, triangles, tripartite graphs, Tuza’s conjecture.

The first author was partially supported by NSERC. The second author was partially supported by CNPq (Proc. 300334/93–1 and ProTeM-CC-II Project ProComb).

a set of three vertices, one from each X_{i}. Ryser conjectured that τ(H) ≤ 2ν(H) for every tripartite hypergraph H, where here ν(H) denotes the maximum size of a set of pairwise disjoint hyperedges of H, and τ(H) is the minimum size of a set of vertices C such that E ∩ C ≠ ∅ for all E ∈ E. The best upper bound for this problem that is currently known [2] is τ(H) ≤ 5ν(H)/2. For more details on Ryser’s conjecture, see Conjecture 4.29 in Füredi [1], and Tuza [5]. Note that if G is a tripartite graph then its edge set can be partitioned into 3 classes such that every triangle in G contains exactly one edge from each class. Therefore T (G), the set of triangles in the graph G, corresponds in an obvious way to the set of hyperedges of a tripartite hypergraph H = H(G), and in our notation τ(G) = τ(H) and ν(G) = ν(H). Thus our main result of this note shows that Ryser’s conjecture is true for hypergraphs that are derived from tripartite graphs in this way.

In §1 of this note we give two lemmas needed in the proof of our main result, Theorem 4. In §2 we give the proof of Theorem 4, and also give examples of tripartite graphs G with τ(G) ≥ 5ν(G)/4.

§1. Two Lemmas

We begin with some definitions and notation. Let G be a tripartite graph with vertex sets V_{1}, V_{2}, and V_{3}, and denote by E_{σ} the set of edges with one endpoint in V_{σ+1} and the other in V_{σ+2} (here addition is taken modulo 3). We sometimes say that the vertices in V_{σ} and the edges in E_{σ} are coloured with colour σ. For a path, triangle or set of triangles S in G, we shall write E(S) for the set of all the edges appearing in S, and E_{σ}(S) for the subset of E(S) consisting of the edges in E_{σ}. In the sequel, if the vertices a, b, and c induce a triangle T = G[{a, b, c}] in a graph G, we shall write abc for this triangle T. Recall that we denote the family of triangles of a graph G by T (G).

Lemma 1. Let σ ∈ {1, 2, 3} be fixed, and let B be an independent set of triangles in G. Then one of the following assertions holds.

(1.1) There exists an independent set of triangles B′ in G with |B′| = |B| + 1 such

that E_{σ′}(B) ⊂ E_{σ′}(B′) for both σ′ ≠ σ. (1.2) We have τ(G) ≤ 2|B|.

Proof. We shall describe how to construct either B′ or a transversal C for G with |C| ≤ 2|B|. Observe that we may clearly assume that B is a maximal independent family of triangles. In other words, we may assume that every triangle in G contains at least one edge of E(B).

For each vertex v ∈ V_{σ}, let B_{v} denote the subset of B consisting of triangles containing v. We define for each v ∈ V_{σ} a bipartite graph H_{v} with vertex set V_{σ+1} ∪ V_{σ+2} as follows. We let xy be an edge of H_{v} if vxy is a triangle in G and xy is not an edge of T for any T ∈ B \ B_{v}. We denote by ν(H_{v}) the maximum size of a matching in H_{v}. Note that B_{v} corresponds to a matching in H_{v}, which we shall denote by M_{v}. Note also that since B is maximal, we have that M_{v} is a maximal matching, i.e., every edge of H_{v} not in M_{v} is adjacent to an edge of M_{v}.

Case 1. For some v ∈ V_{σ}, we have |M_{v}| < ν(H_{v}).

In this case, pick an augmenting path P = x_{1}y_{1}x_{2}y_{2} … x_{k}y_{k} in H_{v}, so that x_{j}y_{j} ∉ M_{v} (1 ≤ j ≤ k), y_{j}x_{j+1} ∈ M_{v} (1 ≤ j < k), and neither x_{1} nor y_{k} is covered by M_{v}.

Then the set of triangles

B′ = (B \ {vyx: yx ∈ E(P) ∩ M_{v}}) ∪ {vxy: xy ∈ E(P) \ M_{v}}

is such that |B′| = |B| + 1. We now check that the set B′ is independent. It is clear that those elements of B′ containing v are independent, as (E(P)\M_{v})∪(M_{v}\E(P)) is a matching in H_{v}. Also, if T ∈ B′ does not contain v then it can intersect a triangle containing v only in the edge of colour σ. But by construction, no edge of colour σ of any triangle in B \ B_{v} appears in H_{v}. Finally we note that E_{σ+1}(B \ B′) ∪ E_{σ+2}(B \ B′) = {vu: u ∈ V (P) \ {x_{1}, y_{k}}} ⊂ E_{σ+1}(B′) ∪ E_{σ+2}(B′). Therefore B′ satisfies the conditions of (1.1), and so this case is finished. Case 2. For all v ∈ V_{σ}, we have |M_{v}| = ν(H_{v}). In this case we describe a transversal C of T (G). For each v ∈ V_{σ} let C_{v} denote a vertex-cover of the edges of H_{v} of minimum size, so |C_{v}| = ν(H_{v}) by the König– Egerváry theorem. We let

C = E_{σ}(B) ∪ ⋃_{v∈V_{σ}}{vz: z ∈ C_{v}}.

Then C is a transversal, since if T ∈ T (G) is such that E(T) ∩ E_{σ}(B) = ∅, then T is represented as an edge e of H_{v} where v is the vertex of T of colour σ, and so vz ∈ E(T) ∩ C where z ∈ C_{v} is a vertex covering e in H_{v}. To estimate |C|, simply notice that ∑_{v∈V_{σ}} |C_{v}| = ∑_{v∈V_{σ}} ν(H_{v}) = |B|. Therefore |C| = 2|B| and hence (1.2) is proved. □

Note that Lemma 1 immediately implies that τ(G) ≤ 2ν(G) for any tripartite graph G. Our aim now is to improve on Lemma 1 taking into account certain special edges present in the family B.

An edge e ∈ E(B) appearing in an independent set of triangles B is said to be essential if there exists a triangle T of G such that E(T) ∩ E(B) = {e}, and we say that such a triangle T is associated with e. We denote by Ē_{σ}(B) the set of edges in E_{σ} that are essential in B, and we let ν_{σ}(B) = |Ē_{σ}(B)|. A refinement of Lemma 1 is as follows.

Lemma 2. Let σ ∈ {1, 2, 3} be fixed, and let B be an independent set of triangles in G. Then one of the following assertions holds. (2.1) There exists an independent set of triangles B′ in G with |B′| = |B| + 1 such

that for both σ′ ≠ σ, we have |E_{σ′}(B) ∩ E_{σ′}(B′)| ≥ |B| − 1. (2.2) We have τ(G) ≤ 2|B| − ν_{σ}(B).

Proof. For each v ∈ V_{σ} we define B_{v}, H_{v}, and M_{v} as in the proof of Lemma 1, and we assume as before that B is maximal, and hence that each M_{v} is a maximal matching in H_{v}.

A vertex x ∈ H_{v} is called v-essential of type 1 if there is an alternating path P (x) = y_{0}x_{1}y_{1}x_{2}y_{2} … x_{k} with x_{1} = x, k ≥ 1, x_{j}y_{j} ∉ M_{v} (1 ≤ j ≤ k) and y_{j}x_{j+1} ∈ M_{v} (0 ≤ j < k), and vx_{k} is an essential edge for B. The vertex x is said to be v-essential of type 2 if the path P (x) as above exists, k ≥ 2, and y_{k−1}x_{k} rather than vx_{k} is an essential edge. A v-essential vertex is one that is v-essential of type 1 or type 2. Note that if x is v-essential then x_{i} is also v-essential for i = 1, …, k − 1, and also so is x_{k} if x is of type 1. We denote by V̄ (H_{v}) the set of v-essential vertices of H_{v}.

To prove Lemma 2, we assume that there does not exist an independent set B′ of triangles as in (2.1) of our lemma, and prove the following assertion.

(*) For every vertex v ∈ V_{σ}, we have (i) each edge of M_{v} is incident with at most one v-essential vertex, (ii) the set C = E_{σ}(B) ∪ C_{2} ∪ C_{3} is a transversal for G, where

C_{2} = {vx: x ∈ V̄ (H_{v})},
C_{3} = {vy: y ∈ V_{σ+1} and wy ∈ M_{v} for some w
such that wy ∉ Ē_{σ}(B), and w, y ∉ V̄ (H_{v})}.

Moreover, |C| ≤ 2|B| − ν_{σ}(B).

We now proceed to prove assertion (*). Let v ∈ V_{σ} be fixed.

Proof of (i). Suppose on the contrary that xz ∈ M_{v} is such that both x and z are v-essential. Let P (x) = zxy_{1}x_{2} … x_{k} and P (z) = xzw_{1}z_{2} … z_{l} be the alternating paths associated with x and z. We may assume that we have chosen the triple (xz, P (x), P (z)) so as to minimise the sum k + l. We shall need the following technical lemma, the proof of which is postponed to the end of this section.

Lemma 3. The paths P (x) and P (z) are vertex-disjoint, except for x and z.

Assuming the result of Lemma 3, we now proceed to derive a contradiction to the assumption that B′ as in (1.1) of the lemma does not exist. We first note that the following statement holds.

(**) The family

\begin{aligned}B′′ = (B & \ \{vab: ab ∈ E(P (x) ∪ P (z)) ∩ M_{v}\}) \\ & ∪ \{vab: ab ∈ E(P (x) ∪ P (z)) \ M_{v}\} \end{aligned}

is an independent set of triangles of size |B| − 1, and

E_{σ+1}(B \ B′′) ∪ E_{σ+2}(B \ B′′) ⊂ E_{σ+1}(B′′) ∪ E_{σ+2}(B′′) ∪ {vx_{k}, vz_{l}}.

Indeed, since [(E(P (x))∪E(P (z)))\M_{v}]∪[M_{v}\(E(P (x))∪E(P (z)))] is a matching in H_{v}, the set B′′_{v} of triangles in B′′ containing v are all edge-disjoint. Also, a triangle in B′′_{v} can intersect a triangle in B′′ \ B′′_{v} = B \ B_{v} only in the edge of colour σ, but this is not possible since the edges in E_{σ}(B \ B_{v}) are not present in H_{v} by construction. Therefore B′′ is independent, and also clearly has size |B| − 1. The edge condition in (**) follows immediately from the definition.

Now to obtain the desired contradiction, we shall show that it is possible to add two more triangles to B′′ to form an independent set of triangles satisfying (2.1) of the lemma. Note that the edge condition in (2.1) will then follow directly from the edge condition in (**). We shall consider three different cases, according to the type of the vertices x and z.

Case 1. The vertices x and z are both of type 1. Let vx_{k}c and vz_{l}d be triangles associated with the v-essential edges vx_{k} and vz_{l} respectively. Let

B′ = B′′ ∪ {vx_{k}c, vz_{l}d}.

Note that vx_{k}c and vz_{l}d are also edge-disjoint from each other and the rest of B′_{v} = {vxy ∈ B′}, since c and d are not incident with any edge of M_{v} as vx_{k} and vz_{l} are essential for B, and hence in particular are not equal to any vertex of P (x) ∪ P (z). Also c ≠ d since they are in different vertex classes. Therefore B′ is a set of pairwise edge-disjoint triangles satisfying (2.1). Case 2. The vertex x is of type 1 and z is of type 2. Let vx_{k}d and cw_{l−1}z_{l} be triangles associated with the v-essential edges vx_{k} and w_{l−1}z_{l} respectively, where v ≠ c ∈ V_{σ}. Let

B′ = B′′ ∪ {vx_{k}d, cw_{l−1}z_{l}}.

The proof that vx_{k}d is edge-disjoint from B′ \ {vx_{k}d, cw_{l−1}z_{l}} is as in Case 1, and the fact that v ≠ c and x_{k} ≠ w_{l−1} is enough to prove that cw_{l−1}z_{l} is edge-disjoint from vx_{k}d. Also, cw_{l−1}z_{l} is edge-disjoint from all of B′ ∩ B since w_{l−1}z_{l} is essential for B and w_{l−1}z_{l} ∈ (E(P (x)) ∪ E(P (z))) ∩ M_{v}, and from B′ \ B since w_{l−1}z_{l} ∉ (E(P (x))∪E(P (z)))\M_{v} and c ≠ v. Therefore B′ is an independent set of triangles that satisfies (2.1). Case 3. The vertices x and z are both of type 2. Let y_{k−1}x_{k}d and cw_{l−1}z_{l} be triangles associated with the v-essential edges y_{k−1}x_{k} and w_{l−1}z_{l} respectively, where c, d ∈ V_{σ} and v ≠ c, d. This time let

B′ = B′′ ∪ {y_{k−1}x_{k}d, cw_{l−1}z_{l}}.

The proof that y_{k−1}x_{k}d and cw_{l−1}z_{l} are edge-disjoint from all of B′ ∩B is as before. Also, w_{l−1}z_{l}, y_{k−1}x_{k} ∉ E(P (x)) ∩ E(P (z))) \ M_{v} and c, d ≠ v imply that y_{k−1}x_{k}d and cw_{l−1}z_{l} are edge-disjoint from B′ \ (B ∪ {y_{k−1}x_{k}d, cw_{l−1}z_{l}}). Finally, y_{k−1}x_{k}d and cw_{l−1}z_{l} share no edges since y_{k−1}x_{k} and w_{l−1}z_{l} are distinct independent edges in H_{v}. Therefore B′ is indeed an independent set of triangles satisfying (2.1).

This completes the proof of assertion (i).

Proof of (ii). We start by showing that C is a transversal for G. Let T = vxy ∈ T (G) where v ∈ V_{σ}, y ∈ V_{σ+1}, and x ∈ V_{σ+2}, and suppose E(T) ∩ E_{σ}(B) = ∅, that is xy ∉ M_{v}. If y were not incident with an edge of M_{v}, then xv would be essential for B, and hence x ∈ V̄ (H_{v}) and so E(T) ∩ C_{2} ≠ ∅. Similarly we are done if x were not incident with an edge of M_{v}, so we may assume that zx and wy are in M_{v} for some w ∈ V_{σ+2} and z ∈ V_{σ+1}. Now if wy were essential for B, then the alternating path P (x) = zxyw would show that x is v-essential, and hence vx ∈ E(T) ∩ C_{2}. Clearly we may also assume that y is not v-essential. Finally, to show that vy ∈ C_{3}, we need to show that w is not v-essential, so suppose on the contrary that it is. Then there exists an alternating path P (w) = ywy_{1}x_{2}y_{2} … x_{k} satisfying the required conditions. Then we claim that x is v-essential with path P (x) = zxP (w). The only condition we need to check is that P (x) is really a path, i.e., we do not have x = x_{i} for some i ∈ {2, …, k} or z = y_{j} for some j ∈ {1, …, k − 1}. If the second of these holds then also x = x_{j+1} since zx ∈ M_{v} is the only edge in M_{v} incident with z. But as noted before, if w is of type 1 then x_{i} is also v-essential for i = 2, …, k, which would imply that x is v-essential. Similarly if w is of type 2 and x = x_{j} for some j ∈ {2, …, k −1} then we are finished. Finally if w is of type 2 and x = x_{k} then P (y) = wyx_{k}y_{k−1} shows that y is v-essential. Therefore if x and y are not v-essential then vy ∈ E(T) ∩ C_{3}. Hence C is a transversal of T (G).

Now |C| = |B| + |C_{2}| + |C_{3}|, and by (i) we have that |C_{2}| = ∑_{v∈V_{σ}} |V̄ (H_{v})| and |C_{3}| = ∑_{v∈V_{σ}} (|M_{v}| − |V̄ (H_{v})| − |M_{v} ∩ Ē_{σ}(B)|). Hence

|C| = |B| + ∑_{v∈V_{σ}} (|M_{v}| − |M_{v} ∩ Ē_{σ}(B)|) = 2|B| − ν_{σ}(B),

proving (ii).

This completes the proof of Lemma 2. □

Proof of Lemma 3. We start by proving that x_{j} ≠ w_{r} for all j and r. First note that x ≠ w_{r} for any r since P (z) is a path. Now suppose that x_{j} = w_{r} for some j ∈ {2, …, k − 1} and r ∈ {1, …, l − 2}. Then since M_{v} is a matching and both y_{j−1}x_{j} and w_{r}z_{r+1} ∈ M_{v}, we have also that y_{j−1} = z_{r+1}. But then y_{j−1}x_{j} ∈ M_{v}, and P (x_{j}) = y_{j−1}x_{j}y_{j} … x_{k} and P (y_{j−1}) = w_{r}z_{r+1}w_{r+1} … z_{l} show that x_{j} and y_{j−1} are v-essential. Therefore the triple (x_{j}y_{j−1}, P (x_{j}), P (y_{j−1})) is a better choice than (xz, P (x), P (z)), which is a contradiction.

Hence x_{j} = w_{r} can happen only if j = k or r = l − 1. To complete the argument we shall now need to consider several cases according to the type of x and z. First note that the above argument is also valid, i.e., P (x_{j}) and P (y_{j−1}) are ‘valid’ alternating paths if x_{j} = w_{r} and any of the following hold:

• j = k, r ≠ l − 1, x is of type 1 and z is of either type,

• r = l − 1, j ≠ k, z is of type 1 and x is of either type,

• j = k, r = l − 1, and both x and z are of type 1. We next consider the case in which j = k, r ≠ l−1, and x is of type 2, i.e., y_{k−1}x_{k} ∈ M_{v} is essential for B. Then again we must have w_{r}z_{r+1} = y_{k−1}x_{k} ∈ M_{v} essential for B, and so P′(z) = xzw_{1} … w_{r}z_{r+1} is a valid shorter path for z, contradicting the fact that k + l is minimal. Similarly, if r = l − 1, j ≠ k, and z is of type 2 then w_{l−1}z_{l} = y_{j−1}x_{j} and P′(x) = zxy_{1}x_{2} … y_{j−1}x_{j} is a valid shorter path for x.

The remaining cases have j = k and r = l−1, so y_{k−1}x_{k} = w_{l−1}z_{l}. If x is of type 2 and z is of type 1, then the triangle vx_{k}y_{k−1} ∈ B has two essential edges y_{k−1}x_{k} and vz_{l}. Let y_{k−1}z_{l}a and vz_{l}b be triangles associated with these essential edges, where v ≠ a ∈ V_{σ}. Then B′ = (B \ {vx_{k}y_{k−1}}) ∪ {y_{k−1}x_{k}a, vz_{l}b} is an independent set of triangles of size |B| + 1 satisfying (2.1) of our lemma. Now if x is of type 1 and z is of type 2, then the same argument applies with the edges y_{k−1}x_{k} and vx_{k} that are essential for B. Therefore the last possibility is that x and y are both of type 2. We shall show that in this case B′ as in (2.1) exists. Let cy_{k−1}x_{k} = cw_{l−1}z_{l} be a triangle associated with the essential edge y_{k−1}x_{k}, so v ≠ c ∈ V_{σ}. Let

B′ = B′′ ∪ {cy_{k−1}x_{k}},

where B′′ is as defined in (**). Here the triangle cy_{k−1}x_{k} is edge-disjoint from any T ∈ B′ \ (B′_{v} ∪ {cy_{k−1}x_{k}}) = B \ B_{v} since cy_{k−1}x_{k} is associated to the essential edge y_{k−1}x_{k} of B, and is edge-disjoint from any T ∈ B′_{v} by construction. Therefore B′ is an independent set of triangles of size |B| + 1, and also the edge condition in (2.1) follows for B′ from (**). This contradiction shows that x_{j} ≠ w_{r} for any j and r. A similar argument shows that y_{j} ≠ z_{r} for any j and r, and so P (x) and P (z) are vertex-disjoint apart from x and z, proving Lemma 3. □

§2. Proof of the Main Result

We now proceed to prove our main result, Theorem 4 below. In the sequel, the edge of colour σ in a triangle T is denoted by e_{σ}(T).

Theorem 4. Let G be a tripartite graph. Then τ(G) ≤ αν(G), where α = (38 + \sqrt{1948})/42 < 1.956.

Proof. The proof is by induction on ν = ν(G). The case ν = 1 is immediate, and hence we assume that ν = ν(G) ≥ 2 and that our theorem holds for graphs G′ with ν(G′) < ν. Let B_{0} be a fixed independent set of triangles in G of size ν. Our first aim is to construct a second large independent set B_{1} of triangles of G. Let G′ denote the graph obtained from G by deleting all edges in E_{1}(B_{0}), let B′ be an independent set of triangles of G′ of maximum size, and let ν′ = |B′|. Case 1. ν′ = ν In this case, we claim that τ(G) ≤ 7ν/4 < αν, which completes the induction step. To prove the claim, let

C_{0} = E_{2}(B_{0}) ∪ E_{2}(B′) ∪ Ē_{3}(B_{0}) ∪ Ē_{3}(B′)

and let T ∈ T (G). Suppose that E(T) ∩ (E_{2}(B_{0}) ∪ E_{2}(B′)) = ∅. Since ν′ = ν it is clear that T must contain an edge of E(B_{0}) and an edge of E(B′). But E_{1}(B_{0}) ∩ E_{1}(B′) = ∅ by construction, so for one of B = B_{0} or B′ we have E(T) ∩ E_{1}(B) = ∅. Therefore E(T)∩E_{3}(B) ≠ ∅, and by definition T shows that e_{3}(T) is essential for B. Thus E(T) ∩ Ē_{3}(B) ≠ ∅, and so we have shown that C_{0} is a transversal.

To estimate |C_{0}|, we first consider |E_{2}(B′) \ E_{2}(B_{0})|. Note that if T ∈ B′ and e_{2}(T) ∉ E_{2}(B_{0}) then T shows that e_{3}(T) is essential for B_{0}. Since any two such T are edge-disjoint, we see that there are at most ν_{3}(B_{0}) = |Ē(B_{0})| such triangles. Therefore |E_{2}(B′) \ E_{2}(B_{0})| ≤ ν_{3}(B_{0}), and hence |C_{0}| ≤ ν + 2ν_{3}(B_{0}) + ν_{3}(B′). Now, by Lemma 2, we are finished if ν_{3}(B_{0}) ≥ ν/4 or ν_{3}(B′) ≥ ν/4, so let us assume that ν_{3}(B_{0}), ν_{3}(B′) < ν/4. But then |C_{0}| ≤ 7ν/4, which proves the claim, and hence this case is finished. Case 2. ν′ < ν In this case, by induction there exists a transversal C′ of G′ of size at most αν′. Notice that C′ ∪ E_{1}(B_{0}) is a transversal for G of size at most ν + αν′, and so we may assume that ν + αν′ > αν, that is, that ν′ > (α − 1)ν/α. We now consider B′ as an independent set of triangles in G. We apply Lemma 1 repeatedly with σ = 2 and σ = 3 to obtain a sequence B′ = B^{1}, B^{2}, …, B^{k} of independent families of triangles in G, where for each i = 1, …, k − 1 we have |B^{i+1}| = |B^{i}| + 1 and E_{1}(B^{i}) ⊂ E_{1}(B^{i+1}), and B^{k} satisfies (1.2) of Lemma 1. Let ν′′ = |B^{k}|. Then by Lemma 1 we know that τ(G) ≤ 2ν′′, and so we may assume that ν′′ > αν/2.

Finally, to obtain B_{1}, we apply Lemma 2 repeatedly with σ = 2 and σ = 3 to obtain a further sequence B^{k}, B^{k+1}, …, B^{f} = B_{1} of independent families of triangles of G, where for each i = k, …, f − 1 we have |B^{i+1}| = |B^{i}| + 1 and |E_{1}(B^{i}) ∩ E_{1}(B^{i+1})| ≥ |B^{i}| − 1. Then by (2.2) of Lemma 2 we have (3) τ(G) ≤ 2|B_{1}| − ν_{σ}(B_{1}) for both σ = 2 and σ = 3.

Let ν_{1} = |B_{1}|. Clearly ν_{1} ≤ ν. By construction we have that |E_{1}(B_{1})∩E_{1}(B′)| ≥ ν′ − (ν_{1} − ν′′), and so

(4)  |E_{1}(B_{1}) ∩ E_{1}(B_{0})| ≤ ν_{1} − |E_{1}(B_{1}) ∩ E_{1}(B′)| ≤ 2ν_{1} − ν′ − ν′′.

Our aim is to choose a set C of edges from E(B_{0})∪E(B_{1}) that will be a transversal of G of suitable size. We shall select C based on the following assertion. (†) One of the following holds:

(a) |E_{2}(B_{1}) \ E_{2}(B_{0})| ≤ ν_{3}(B_{0}) + \frac{1}{2}ν_{1}(B_{0}) + ν − \frac{1}{2}(ν′ + ν′′), or

(b) |E_{3}(B_{1}) \ E_{3}(B_{0})| ≤ ν_{2}(B_{0}) + \frac{1}{2}ν_{1}(B_{0}) + ν − \frac{1}{2}(ν′ + ν′′).

Consider first the set S of triangles T ∈ B_{1} for which e_{1}(T) ∈ E_{1}(B_{1}) ∩ E_{1}(B_{0}). Note that clearly |S| = |E_{1}(B_{1}) ∩ E_{1}(B_{0})|. If T ∈ S and both e_{2}(T) ∉ E_{2}(B_{0}) and e_{3}(T) ∉ E_{3}(B_{0}), then T shows that e_{1}(T) is essential for B_{0}. Therefore the number of such triangles T is at most ν_{1}(B_{0}). Hence at least |E_{1}(B_{1})∩E_{1}(B_{0})|−ν_{1}(B_{0}) of the triangles T ∈ S are such that either e_{2}(T) ∈ E_{2}(B_{0}) or e_{3}(T) ∈ E_{3}(B_{0}). Thus for one of σ = 2 or σ = 3 we have that at most ν_{1}(B_{0})+(|E_{1}(B_{1})∩E_{1}(B_{0})|−ν_{1}(B_{0}))/2 triangles in S are such that e_{σ}(T) ∉ E_{σ}(B_{0}). Let us first suppose that here σ = 2, and we proceed to prove that (a) holds. The proof for (b) is exactly the same if σ = 3.

Now we look at B_{1} \S. If T ∈ B_{1} \S then e_{1}(T) ∉ E_{1}(B_{0}). If also e_{2}(T) ∉ E_{2}(B_{0}) then T shows that e_{3}(T) is essential for B_{0}. Thus the number of T ∈ B_{1} \ S for which e_{2}(T) ∉ E_{2}(B_{0}) is at most ν_{3}(B_{0}). Hence altogether the number of T ∈ B_{1} for which e_{2}(T) ∉ E_{2}(B_{0}) is at most ν_{3}(B_{0}) + (|E_{1}(B_{1}) ∩ E_{1}(B_{0})| + ν_{1}(B_{0}))/2, that is

|E_{2}(B_{1}) \ E_{2}(B_{0})| ≤ ν_{3}(B_{0}) + \frac{1}{2}ν_{1}(B_{0}) + ν − \frac{1}{2}(ν′ + ν′′),

where we use (4). This proves (a), and hence assertion (†).

To finish the proof of Case 2, we construct a suitable transversal C for G. In what follows, we assume without loss of generality that (a) holds in assertion (†). Let

C = Ē_{3}(B_{0}) ∪ Ē_{3}(B_{1}) ∪ E_{2}(B_{0}) ∪ E_{2}(B_{1}) ∪ (E_{1}(B_{0}) ∩ E_{1}(B_{1})),

and we claim that C is a transversal of T (G). To see this, suppose that T ∈ T (G) and E(T) ∩ {E_{2}(B_{0}) ∪ E_{2}(B_{1}) ∪ (E_{1}(B_{1}) ∩ E_{1}(B_{0}))} = ∅. Then for one of B = B_{0} or B_{1}, we have that e_{1}(T) ∉ E_{1}(B) and e_{2}(T) ∉ E_{2}(B). Hence e_{3}(T) is essential for B, and E(T)∩(Ē_{3}(B_{0})∪Ē_{3}(B_{1})) ≠ ∅, which shows that C is indeed a transversal for G.

Now it only remains to estimate |C|. Using (4) and assertion (†)(a), we have

|C| ≤ ν_{3}(B_{0}) + ν_{3}(B_{1}) + ν

+ ν_{3}(B_{0}) + \frac{1}{2}ν_{1}(B_{0}) + ν − \frac{1}{2}(ν′ + ν′′) + 2ν − ν′ − ν′′

= 2ν_{3}(B_{0}) + ν_{3}(B_{1}) + \frac{1}{2}ν_{1}(B_{0}) + 4ν − \frac{3}{2}(ν′ + ν′′).

Now, by (3) and Lemma 2, for each pair (σ, i) ∈ {(3, 1), (3, 0), (1, 0)} there is a transversal of T (G) of size at most 2ν −ν_{σ}(B_{i}). Therefore we may assume that each

.^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}• • • •  • • • • •  ^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} • • •  •  •  • • • •} Figure 1. The graphs H_{1} and H_{2}

of ν_{3}(B_{0}), ν_{1}(B_{0}), and ν_{3}(B_{1}) is less than (2 − α)ν. Further recall that ν′′ > αν/2 and ν′ > (α − 1)ν/α. Hence

\begin{aligned}|C| & ≤ \frac{7}{2}(2 − α)ν + 4ν − \frac{3}{2}(ν′ + ν′′) \\ & ≤ ν (11 − \frac{7}{2}α − \frac{3}{2} (\frac{α − 1}{α} + \frac{1}{2}α)) = \frac{ν}{4α}(6 + 38α − 17α^{2}) ≤ αν. \end{aligned}

This finishes the induction step in this case and the theorem is proved. □

We close with the remark that finding examples of tripartite graphs G with τ(G)/ν(G) much larger than 1 seems difficult. The graphs H_{1} and H_{2} in Figure 1 are such that τ(G) = 5ν(G)/4. Therefore any graph G whose blocks are isomorphic to copies of K^{2}, H_{1} or H_{2} will be such that τ(G) ≥ 5ν(G)/4.

References

1. Füredi, Z., Matchings and covers in hypergraphs, Graphs and Combinatorics 4 (1988), 115– 206.

2. Haxell, P.E., A note on a conjecture of Ryser, Periodica Math. Hungar. 30 (1995), 73–79.

3. Krivelevich, M., On a conjecture of Tuza about packing and covering of triangles, Discrete Math. 142 (195), 281–286.

4. Tuza, Zs., Conjecture, Finite and Infinite Sets (Eger, Hungary 1981) (Hajnal, A., Lovász, L., Sós, V.T., eds.), Proc. Colloq. Math. Soc. J. Bolyai, Vol. 37, North-Holland, Amsterdam, 1984, p. 888.

5. , Ryser’s conjecture for transversals of r-partite hypergraphs, Ars Combinatoria 16(B) (1983), 201–209.

6. , A conjecture on triangles of graphs, Graphs and Combinatorics 6 (1990), 373–380.

Department of Combinatorics and Optimisation, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

   E-mail address: <pehaxell@math.uwaterloo.ca>

Instituto de Matemática e Estatística, Universidade de São Paulo, Cidade Universitária, Rua do Matão 1010, 05508–900 São Paulo, SP, Brazil

   E-mail address: <yoshi@ime.usp.br>