2 The number of edge-disjoint spanning trees of a complete 3- partite graph

(1)

The generalized connectivity of

complete equipartition 3-partite graphs

Shasha Li, Wei Li, Xueliang Li Center for Combinatorics and LPMC-TJKLC

Nankai University, Tianjin 300071, China.

Email: [email protected], [email protected], [email protected]

Abstract

Let G be a nontrivial connected graph of order n, and k an integer with 2 ≤ k ≤ n.

For a setS ofkvertices ofG, letκ(S) denote the maximum number `of edge-disjoint trees T1, T2, . . . , T` in Gsuch thatV(Ti)∩V(Tj) =S for every pair of distinct integersi, j with 1 ≤ i, j ≤`. Chartrand et al. generalized the concept of connectivity as follows: Thek- connectivityofG, denoted byκk(G), is defined byκk(G) =min{κ(S)}, where the minimum is taken over allk-subsetsSofV(G). Thusκ2(G) =κ(G), whereκ(G) is the connectivity of G; whereas,κn(G) is the maximum number of edge-disjoint spanning trees contained inG.

This paper mainly focuses on the k-connectivity of complete equipartition 3-partite graphsK_b³, whereb≥2 is an integer. First, we obtain the number of edge-disjoint spanning trees of a general complete 3-partite graphKx,y,z, which isb^xy+yz+zx_x+y+z−1c. Then, based on this result, we get thek-connectivity ofK_b³for all 3≤k≤3b. Namely,

κk(K_b³) =









 b^d^k

2

3e+k²−2kb

2(k−1) c+ 3b−k if k≥ ^3b₂;

b^3b₂c if k < ^3b₂ andk= 0 (mod3);

b^3bk+3b−k+1_2k+1 c if ^3b₄ < k <^3b₂ andk= 1 (mod3);

b3bk+6b−2k+1

2k+2 c if b≤k < ^3b₂ andk= 2 (mod 3);

b^3b+1₂ c otherwise.

Keywords: k-connectivity, complete equipartition 3-partite graph, internally disjoint trees.

AMS subject classification 2010: 05C40, 05C05.

1 Introduction

We follow the book [1] for all graph theoretical notation and terminology not defined here.

There is an equivalent definition of the connectivity κ(G) of a graph G provided by a well- known theorem of Whitney [9]. For each 2-subset S ={u, v} of the vertex set V(G), let κ(S) denote the maximum number of internally disjoint uv-paths in G. Then κ(G) = min{κ(S)}, where the minimum is taken over all 2-subsets S of V(G). In [3], the authors generalized this definition and proposed the concept of generalized connectivity.

LetGbe a nontrivial connected graph of ordern, andkan integer with 2≤k≤n. For a set S ofkvertices ofG, letκ(S) denote the maximum number`of edge-disjoint treesT₁, T₂, . . . , T_` inG such that V(T_i)∩V(T_j) =S for every pair of distinct integers i, j with 1≤i, j ≤`(note that the trees are vertex-disjoint in G\S). A collection {T₁, T₂, . . . , T_`} of trees inG with this

(2)

property is called a set ofinternally disjoint trees connectingS. Thegeneralizedk-connectivityof G, abbreviated ask-connectivity ofG, denoted byκ_k(G), is then defined asκ_k(G) = min{κ(S)}, where the minimum is taken over all k-subsetsS of V(G).

From a theoretical perspective, both extremes of κ_k are fundamental concepts in graph theory. κ₂(G) = κ(G) is the connectivity of G, and κ_n(G) is the maximum number of edge- disjoint spanning trees contained in G. The concept of edge-disjoint spanning trees is another subject we studied. To motivate the edge-disjoint spanning trees problem, assume that our graph represents a communication network, and that for every choice of two vertices we want to be able to find k edge-disjoint paths between them. Menger’s theorem [4] tells us that such paths exist as soon as our graph is k-edge-connected, which is clearly also necessary. But the theorem does not tell us how to find those paths; in particular, having found them for one pair of endvertices we are not necessarily better placed to find them for another pair. However, if our graph haskedge-disjoint spanning trees, there will always beksuch paths, one in each tree.

Once we have stored those trees in our computer, we shall always be able to find the k paths quickly, for any given pair of endvertices. For edge-disjoint spanning trees of a finite graph G, Nash-Williams and Tutte proved the following theorem independently:

Theorem 1.1 (Nash-Williams [5], Tutte [6]) A multigraph contains k edge-disjoint spanning trees if and only if for every partition P of its vertex set it has at leastk(|P| −1) cross-edges.

As a consequence of this theorem, Corollary 1.2 gives a sufficient condition for the existence of k edge-disjoint spanning trees.

Corollary 1.2 (Diestel [2]) Every2k-edge-connected multigraphGhaskedge-disjoint spanning trees.

According to this corollary, Kriesell conjectured a more general statement: Defining a setS ⊆ V(G) to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. For more details about the spanning tree packing problem, see [13].

From a practical perspective, generalized connectivity can measure the reliability and security of a network. Here is an example. Imagine that a given graph represents a communication network. Suppose that k vertices of the graph are users and other vertices are switchers. The users hope that they can communicate on as many frequencies as possible, so that they can communicate with each other in secrecy even if some of the frequencies are subject to interference or eavesdropping. Users can communicate via a tree connecting all users on each frequency. To avoid interference, each edge can carry only one frequency. And in order to ensure secrecy, each switcher can switch only one frequency. So in essence we need to find the maximum number of internally disjoint trees connecting all users. In a communication network, any knodes may become users and other nodes become switchers. Thus the reliability and security of a network can be measured by its generalized connectivity.

Since Chartrand et al. introduced the concept of generalized connectivity in 1984 [3], there have been only few results about it until they calculatedκ_k(K_n) for every pair of integers k, n with 2 ≤k≤n in 2010 in [7]. Since then, more and more mathematicians begin to study the generalized connectivity and get some progress. In [8] the authors gave the sharp bounds of the generalized 3-connectivity κ₃(G). They also studied the bounds ofκ₃(G) for planar graphs. In [14] we calculatedκ_k(K_a,b) for any two integersa, bwith 1≤a≤band 2≤k≤a+b. In [8] and

(3)

[10] the authors studied the computational complexity of the generalized connectivity of graphs.

In [11] the authors studied the generalized 3-connectivity of Cartesian product graphs. In [12]

the authors studied the minimal size among graphs with the generalized 3-connectivityκ₃= 2.

A complete equipartition 3-partite graph is a complete 3-partite graph in which every part contains exactlybvertices for some integerb. We denote this graph byK_b³. Actually, all vertices in the same part of K_b³ are equivalent. So instead of considering all k-subsets S of V(K_b³), we can restrict our attention to the k-subsetsS_x,y,z ={u₁, u₂, . . . , u_x, v₁, v₂, . . . , v_y, w₁, w₂, . . . , w_z} for 0≤ x, y, z ≤k with x+y+z =k. Moreover, since the three parts U, V and W have the same order, S_x,y,z and S_α,β,γ are equivalent, where α, β, γ is any permutation of x, y, z. So we can assume that b ≥ x ≥ y ≥ z ≥ 0. If z = 0, obviously min{κ(S_x,y,0)} = b+κ_k(K_b,b). So we will restrict our attention to the case that b ≥x ≥y ≥z > 0. For convenience, we denote U_x ={u₁, u₂, . . . , u_x},V_y ={v₁, v₂, . . . , v_y} and W_z ={w₁, w₂, . . . , w_z}.

In the next two sections, we will give the number of edge-disjoint spanning trees in a complete 3-partite graph K_x,y,z and get thek-connectivity ofK_b³ for all 3≤k≤3b, respectively.

2 The number of edge-disjoint spanning trees of a complete 3- partite graph

Before we give the number of edge-disjoint spanning trees of a general complete 3-partite graph K_x,y,z, we will introduce a method to find b_a+b−1^ab c edge-disjoint spanning trees of a complete bipartite graph K_a,b quickly and conveniently. Without loss of generality, we can assume that a≤b.

The List Method

Step 1. Calculatet=b_a+b−1^ab c.

Step 2. Assign appropriate values tod_j for 1≤j≤a. The method of assigning appropriate values to d_j was introduced in [14]. Generally speaking, consider the numbers 1, t+ 1,2t+ 1, . . . ,(a−1)t+ 1, where addition is performed moduloa. If 1, t+ 1,2t+ 1, . . . ,(a−1)t+ 1 are pairwise distinct, we can assign the values to d_j as follows: Let a+b−1 = ka+c, where k, c are integers, and 0 ≤ c ≤ a−1. Then a+b−1 = (k+ 1)c+k(a−c). If c = 0, let d_j = k for all 1 ≤ j ≤ a. If c > 0, let d_(i−1)t+1 = k+ 1 for all 1 ≤ i ≤ c, and let the other d_j = k.

If some of the numbers 1, t+ 1,2t+ 1, . . . ,(a−1)t+ 1 are equal, we can order 1,2, . . . , a by 1, t+ 1,2t+ 1, . . . ,(j−1)t+ 1,2, t+ 2,2t+ 2, . . . ,(j−1)t+ 2, . . . , s, t+s,2t+s, . . . ,(j−1)t+s.

Then we can assign the values of d_j as follows: Let a+b−1 =ka+c, where k, c are integers, and 0≤c≤a−1. Thena+b−1 = (k+ 1)c+k(a−c). In the case that c= 0, let d_j =k for all 1≤ j ≤a. In the case that c > 0 for the first c numbers of our ordering, if d_j uses one of them as subscript, then d_j =k+ 1; elsed_j =k.

Step 3. Form a list with row headings of u₁, . . . , u_a and column headings of v₁, . . . , v_b. Denote the entry in row u_i and columnv_j bya_i,j.

Step 4. According to the assignment ofd_jfor 1≤j≤a, mark the edges of the first spanning tree by 1 in the list. Namely, for every rowu_i with 1≤i≤a, puta_i,d₁_+d₂_+···+d_i−1_−(i−2) =· · ·= a_i,d₁_+d₂_+···+d_i_−(i−1)= 1.

Step 5. For every row u_i with 1 ≤ i ≤ a, mark the entry next to the last 1, namely a_i,d₁_+d₂_+···+d_i_−(i−2), by 2. For every rowu_i with 1≤i≤a−1, mark the entry just above the 2 of rowu_i+1, namelya_i,d₁_+d₂_+···+d_i+1_−(i−1), by 2. For rowu_a, mark the entry in the same column as the last 1 of row u₁, namely a_a,d₁, by 2. Finally, for every row u_i with 1≤i≤a, mark the

(4)

entries between the two 2 by 2. Thus the edges marked by 2 consist of a spanning treeT₂. Step 6. For`with 3≤`≤t, we can find a spanning treeT_` similarly. For every rowu_i with 1≤i≤a, mark the entry next to the last`−1 by`. For every row u_i with 1≤i≤a−1, mark the entry just above the` of rowu_i+1 by `. For row u_a, mark the entry in the same column as the last `−1 of rowu₁ by `. Finally, for every rowu_i with 1≤i≤a, mark the entries between the two`by `. Thus the edges marked by`consist of a spanning treeT_`.

Finally, we find all b_a+b−1^ab c edge-disjoint spanning trees.

If`is less thant=b_a+b−1^ab c, similarly we can use this method to find`edge-disjoint spanning trees ofK_a,bsuch that for every pair of verticesu_iandu_j with 1≤i, j≤a, the difference between the number of unused edges incident withu_i and the number of unused edges incident withu_j is at most 1. For every pair of verticesv_i and v_j with 1≤i, j≤b, we also can use this method to find ` edge-disjoint spanning trees of K_a,b such that the difference between the number of unused edges incident with v_i and the number of unused edges incident with v_j is at most 1.

Just replacet=b_a+b−1^ab c by `.

With this method, we can prove the next theorem.

Theorem 2.1 For a complete 3-partite graph K_x,y,z, we have κ_x+y+z(K_x,y,z) =bxy+yz+zx

x+y+z−1c.

Proof. Let U = {u₁, . . . , u_x}, V = {v₁, . . . , v_y} and W = {w₁, . . . , w_z} be the three parts of K_x,y,z. Without loss of generality, we may assume that z ≤ y ≤ x. Since K_x,y,z contains xy+yz+zxedges and a spanning tree needs x+y+z−1 edges, the number of edge-disjoint spanning trees of K_x,y,z is at most b^xy+yz+zx_x+y+z−1c, namely, κ_x+y+z(K_x,y,z) ≤ b^xy+yz+zx_x+y+z−1c. Thus, it suffices to prove that κ_x+y+z(K_x,y,z) ≥ b^xy+yz+zx_x+y+z−1c. To this end, we want to find out all the b^xy+yz+zx_x+y+z−1c edge-disjoint spanning trees. In other words, we will prove that after we have found some edge-disjoint spanning trees ofK_x,y,z, the number of unused edges is at mostx+y+z−2, namely they are not enough to form a spanning tree.

Firstly, consider the complete bipartite graph K_y,x, which is a subgraph of K_x,y,z. We can use The List Method to find b_y+x−1^yx c edge-disjoint spanning trees of K_y,x, and leave at most y+x−2 unused edges. If we connect each w_i to some spanning tree of K_y,x, we can get a spanning tree ofK_x,y,z. So we can get b_y+x−1^yx c edge-disjoint spanning trees ofK_x,y,z as long as we guarantee that the edges which we used to connectw_iare all distinct. So we can first use The List Method to findt=b^z(y+x)−z(b

yx y+x−1c)

z+y+x−1 cspanning trees ofK_z,y+x. Now, since for every pair of verticesw_i andw_j with 1≤i, j≤z, the difference between the number of unused edges incident withw_iand the number of unused edges incident with w_j is at most 1, everyw_i is incident with at least b_y+x−1^yx c unused edges. So we can indeed find b_y+x−1^yx c edge-disjoint spanning trees of K_x,y,z. Now the number of unused edges is at mosty+x−2 +z+y+x−2<2(z+y+x−1).

If it is less than z+y+x−1, we are done. If it is at least z+y+x−1, we need to find one more spanning tree using the rest unused edges.

Let R be the set of the rest unused edges. If G= (V, R) is connected, we are done. If there are at least two components inG= (V, R), there must be a component containing a cycle. Since

|R| ≥ z+y+x−1 and the number of unused edges in K_y,x is at mosty+x−2, the number of unused edges in K_z,y+x is at least z+ 1. According to The List Method, eachw_i has almost the same number of unused edges. So each w_i has degree at least 1 in G. Again, according to The List Method, the unused edges in K_y,x can not form a cycle, neither can the unused edges

(5)

inK_z,y+x. So the component containing a cycle must contain some unused edges both inK_y,x and in K_z,y+x. And the cycle must be one of the two cases shown in Figure 1. In case 1, w_iu_j and u_jv_k are edges andw_iv_k is a path. In case 2,w_iv_k and u_jv_k are edges and w_iu_j is a path.

Now consider another component. Without loss of generality, we can assume that it contains a vertex u_q. If the cycle is the first case, we can exchange the signs of column u_j and column u_q in the list ofK_z,y+x, but keep the list of K_y,x unchanged. Namely, for every vertex w_i with 1 ≤i≤z, which is adjacent to exactly one of u_j and u_q originally, say u_j, now w_i is adjacent tou_q, the other one of the two vertices. But the other adjacency relations are kept unchanged.

Similarly, if the cycle is the second case, we can exchange the signs of column v_k and column u_q in the list of K_z,y+x, but keep the list of K_y,x unchanged. Now with the new list, we have the edges w_iu_q,u_jv_k. Since u_q and u_j(v_k) can not appear in the original path w_iv_k(w_iu_j), the path still exists and keeps unchanged. Then the two components become one, but the other components remain the same as before. So the total number of components is reduced by 1.

Repeating the procedure, we can finally make G connected and find out a spanning tree of G.

Now the number of rest unused edges is less than z+y+x−1. So we have already found b^xy+yz+zx_x+y+z−1c edge-disjoint spanning trees of K_x,y,z, and hence, κ_x+y+z(K_x,y,z) ≥ b^xy+yz+zx_x+y+z−1c. So we have proved that κ_x+y+z(K_x,y,z) =b^xy+yz+zx_x+y+z−1c.

w_i

u_j v_k

w_i

u_j v_k

case 1 case 2

Figure 1. The component containing a cycle.

3 The k-connectivity of a complete equipartition 3-partite graph

For simplicity, denote K_b³ by G. Now, let A₀ be the set of trees connecting S_x,y,z whose vertex set is S_x,y,z, let A₁ be the set of trees connectingS_x,y,z whose vertex set is S_x,y,z∪ {u}, where u /∈ S_x,y,z, and let A₂ be the set of trees connecting S_x,y,z whose vertex set is S_x,y,z∪ {u, v}, whereu, v /∈S_x,y,z and they belong to distinct parts.

Lemma 3.1 Let A be a maximum set of internally disjoint trees connecting S_x,y,z. Then we can always find a set A⁰ of internally disjoint trees connecting S_x,y,z, such that |A|=|A⁰ |and A⁰ ⊂A₀∪A₁∪A₂.

Proof. Let A={T₁, T₂, . . . , T_p}. If for some tree T_j in A,T_j ∈/ A₀∪A₁∪A₂, then let V(T_j) = S_x,y,z∪U⁰∪V⁰ ∪W⁰, where (U⁰∪V⁰ ∪W⁰)∩S_x,y,z = ∅, U⁰ ⊆ U, V⁰ ⊆ V and W⁰ ⊆ W. At most two of U⁰, V⁰ and W⁰ can be empty. If at least two of them are nonempty, say U⁰, V⁰, let u⁰ ∈ U⁰ and v⁰ ∈ V⁰. The tree T_j⁰ with vertex set V(T_j⁰) = S_x,y,z∪ {u⁰, v⁰} and edge set E(T_j⁰) ={u⁰w₁, . . . , u⁰w_z, u⁰v₁, . . . , u⁰v_y, v⁰u₁, . . . , v⁰u_x, u⁰v⁰}is a tree inA₀∪A₁∪A₂ (See Figure 2). Since V(T_j)∩V(T_i) = S_x,y,z and E(T_j)∩E(T_i) = ∅ for every tree T_i ∈ A, where i 6= j, T_i does not containu⁰, v⁰ nor the edges incident with u⁰, v⁰. Therefore, V(T_j⁰)∩V(T_i) =S_x,y,z and E(T_j⁰)∩E(T_i) = ∅ for 1 ≤ i ≤ p, i 6= j. If exactly one of U⁰, V⁰ and W⁰ is nonempty,

(6)

say U⁰, let U⁰ ={u⁰₁, u⁰₂, . . . , u⁰_q}. Then we delete u⁰₂, . . . , u⁰_q. It may produce some connected components. For each component which does not contain u⁰₁, there must be an edge connecting one of u⁰₂, . . . , u⁰_q with it originally. Thus each component which does not contain u⁰₁ must contain a vertex in V ∪W. Find such a vertex and connect it with u⁰₁ by an edge. Obviously, the new graph we obtain is a tree T_j⁰ ∈ A₀ ∪A₁ ∪A₂ that connects S_x,y,z (See Figure 3).

For every tree T_i ∈ A, where i 6= j, T_i does not contain u⁰₁ nor the edges incident with u⁰₁. Therefore, V(T_j⁰)∩V(T_i) =S_x,y,z and E(T_j⁰)∩E(T_i) =∅ for 1≤ i≤p, i6= j. Replacing each T_j ∈/A₀∪A₁∪A₂ byT_j⁰, we finally get the setA⁰⊂A₀∪A₁∪A₂ which has the same cardinality asA.

· · ·

u₁ u₂ u_x u⁰ u⁰⁰

v₁ v₂ v

y v⁰

w1 w₂ w

z w⁰

· · ·

· · · u₁ u₂ u

x u⁰

v₁ v₂ v

y v⁰

w₁ w₂ w

z

Figure 2. IfU⁰ and V⁰ are not empty.

· · ·

· · · u₁ u₂ u

x u⁰

1 u⁰

2 u⁰

q

v₁ v₂

vy

w₁ w₂ w_z

· · ·

· · · u₁ u₂ u

x u⁰

1

v₁ v₂ v_y

w₁ w₂ w_z

Figure 3. If only U⁰ is nonempty.

So, we can assume that the maximum set A of internally disjoint trees connecting S_x,y,z is contained in A₀∪A₁∪A₂. Next, we will define the standard structure of trees in A₀, A₁ and A₂, respectively.

Every tree inA₀ is of standard structure. A treeT inA₁with vertex setV(T) =S_x,y,z∪ {u}, whereu∈U\S_x,y,z, is of standard structure ifuis adjacent to every vertex inS_x,y,z∩(V ∪W).

Since |E(T)| = |V(T)| −1 = k and d_T(u) = |S_x,y,z∩(V ∪W)| = k−x, there are x edges incident with S_x,y,z ∩U. We know that |S_x,y,z ∩U| = x and each vertex must have degree at least 1 in T. So every vertex in S_x,y,z ∩U has degree 1. A tree T in A₁ with vertex set V(T) =S_x,y,z∪ {v}, wherev∈V \S_x,y,z, is of standard structure ifvis adjacent to every vertex inS_x,y,z∩(U∪W). Similarly, every vertex inS_x,y,z∩V has degree 1. A treeT inA₁ with vertex setV(T) =S_x,y,z∪ {w}, wherew∈W \S_x,y,z, is of standard structure ifw is adjacent to every vertex inS_x,y,z∩(U∪V). Similarly, every vertex inS_x,y,z∩W has degree 1. A treeT inA₂ with

(7)

vertex setV(T) =S_x,y,z∪ {u, v}, where u /∈S_x,y,z,v /∈S_x,y,z and u,v belong to distinct parts, is of standard structure ifu is adjacent tov and every vertex inS_x,y,z is adjacent to exactly one of u, v. We then denote the set of trees in A₀, A₁ and A₂ with the standard structure by A₀, A₁ and A₂, respectively. Clearly,A₀ =A₀.

Lemma 3.2 Let A be a maximum set of internally disjoint trees connecting S_x,y,z, A ⊂ A₀∪ A₁∪A₂. Then we can always find a set A⁰⁰ of internally disjoint trees connecting S_x,y,z, such that |A|=|A⁰⁰| andA⁰⁰⊂ A₀∪ A₁∪ A₂.

Proof. Let A = {T₁, T₂, . . . , T_p}. Suppose that there is a tree T_j in A such that T_j ∈ A₁, but T_j ∈ A/ ₁. Let V(T_j) =S_x,y,z∪ {u}, where u∈U\S_x,y,z. Note that the case u ∈V \S_x,y,z and the case u∈W \S_x,y,z are similar. Since T_j ∈ A/ ₁, there are some vertices inS_x,y,z∩(V ∪W), sayv⁰₁, . . . , v_s⁰, w⁰₁, . . . , w⁰_t, not adjacent tou. Then we can connectv⁰₁ tou by a new edge. It will produce a unique cycle. Delete the other edge incident withv₁⁰ on the cycle. The graph remains a tree. Do the same operation on v⁰₂, . . . , v_s⁰, w⁰₁, . . . , w⁰_t in turn. Finally we get a tree T_j⁰ whose vertex set isS_x,y,z∪ {u}and u is adjacent to every vertex in S_x,y,z∩(V ∪W), that is, T_j⁰ is of standard structure. For each tree T_r ∈ A\ {T_j}, clearly T_r does not contain u nor the edges incident withu. SoV(T_j⁰)∩V(T_r) =S_x,y,z andE(T_j⁰)∩E(T_r) =∅. Suppose that there is a tree T_j inAsuch thatT_j ∈A₂, butT_j ∈ A/ ₂. LetV(T_j) =S_x,y,z∪ {u, v}, whereu, v /∈S_x,y,z and they belong to distinct parts. Without loss of generality, suppose thatu∈U\S_x,y,zandv∈V\S_x,y,z. If u and v are not adjacent, connect u and v by the edge uv. It will produce a unique cycle.

Delete the other edge incident with u on the cycle. Then for every vertex w ∈ S_x,y,z, if w is adjacent to neither u nor v, connect w with an edge to one of them which is in the different part fromw. It will produce a unique cycle. Delete the other edge incident withwon the cycle.

The graph remains a tree, denoted by T_j⁰. By our operation, T_j⁰ is a tree in A₂. For each tree T_r∈A\ {T_j},V(T_j⁰)∩V(T_r) =S_x,y,z andE(T_j⁰)∩E(T_r) =∅. Replacing eachT_j ∈ A/ ₀∪ A₁∪ A₂ by T_j⁰, we finally get the set A⁰⁰⊂ A₀∪ A₁∪ A₂ which has the same cardinality asA.

So, we can assume that the maximum set A of internally disjoint trees connecting S_x,y,z is contained inA₀∪ A₁∪ A₂. Namely, all trees inA are of standard structure.

For simplicity, we denote the union of the vertex sets of all trees in set A by V(A) and the union of the edge sets of all trees in set A by E(A). Let A₀ := A∩ A₀, A₁ := A∩ A₁ and A₂ :=A∩ A₂. Then A=A₀∪A₁∪A₂.

Lemma 3.3 Let A ⊂ A₀∪ A₁ ∪ A₂ be a maximum set of internally disjoint trees connecting S_x,y,z. Then at most one of U \V(A),V \V(A) and W \V(A) is nonempty.

Proof. If at least two of U \V(A), V \V(A) and W \V(A) are nonempty, without loss of generality, let u ∈ U \ V(A) and v ∈ V \V(A). Then the tree T⁰ ∈ A₂ with vertex set V(T⁰) =S_x,y,z∪ {u, v}and edge set E(T⁰) ={u₁v, . . . , u_xv, v₁u, . . . , v_yu, w₁u, . . . , w_zu, uv}is a tree that connectsS_x,y,z. Moreover,V(T⁰)∩V(A) =S_x,y,z and since all edges ofT⁰ are incident withuorv,T⁰ andT are edge-disjoint for any treeT ∈A. So,A∪ {T⁰}is also a set of internally disjoint trees connectingS_x,y,z, contradicting to the maximality of A.

Lemma 3.4 Let A ⊂ A₀∪ A₁ ∪ A₂ be a maximum set of internally disjoint trees connecting S_x,y,z, and A = A₀ ∪A₁ ∪A₂. If V(A) 6= V(G) and A₀ 6= ∅, then we can find a maximum set A⁰ = A⁰₀∪A⁰₁∪A⁰₂ of internally disjoint trees connecting S_x,y,z, such that |A⁰₀| =|A₀| −1,

|A⁰₁|=|A₁|+ 1, and A⁰₂ =A₂.

(8)

Proof. Let u ∈ V(G)\V(A) and T ∈ A₀. Without loss of generality, suppose u ∈ U. Then we can add the edge uv₁ to T and get a tree T⁰ ∈ A₁. Using the method in Lemma 3.2, we can transform T⁰ into a treeT⁰⁰ of standard structure. Then T⁰⁰∈ A₁. Since for T_j ∈A\ {T}, T_j does not contain u nor the edges incident with u and E(T_j)∩E(T) = ∅, T⁰⁰ and T_j are edge-disjoint, and V(T⁰⁰)∩V(T_j) =S_x,y,z . LetA⁰₀:=A₀\ {T},A⁰₁ :=A₁∪ {T⁰⁰} andA⁰₂=A₂. It is easy to see that A⁰ = A⁰₀∪A⁰₁ ∪A⁰₂ is a set of internally disjoint trees connecting S_x,y,z. Since |A⁰₀|=|A₀| −1,|A⁰₁|=|A₁|+ 1, and A⁰₂ =A₂,A⁰ is a maximum set of internally disjoint trees connectingS_x,y,z we want to find.

So, we can assume that for the maximum set Aof internally disjoint trees connectingS_x,y,z, either V(A) =V(G) or A₀ = ∅. Moreover, if A⁰ is a set of internally disjoint trees connecting S_x,y,z which we find currently,V(A⁰) 6=V(G) and the edges in E(G[S_x,y,z])\E(A⁰) can form a tree T inA₀, then by Lemma 3.4 we will add to A⁰ a tree T⁰⁰ ∈ A₁ rather than a tree T ∈ A₀ to form a larger set of internally disjoint trees connectingS_x,y,z. In a similar way, we can prove the following lemma.

Lemma 3.5 Let A ⊂ A₀∪ A₁ ∪ A₂ be a maximum set of internally disjoint trees connecting S_x,y,z, andA=A₀∪A₁∪A₂. IfV(A)6=V(G),(V(G)\V(A))⊆X andV(A₁)\(S_x,y,z∪X)6=∅, where X=U, V,or W, then we can find a maximum setA⁰ =A⁰₀∪A⁰₁∪A⁰₂ of internally disjoint trees connecting S_x,y,z, such that A⁰₀ =A₀, |A⁰₁|=|A₁| −1, and |A⁰₂|=|A₂|+ 1.

Lemma 3.6 We can always find a maximum setAof internally disjoint trees connectingS_x,y,z, such that V(A) =V(G).

Proof. Let A be the maximum set of internally disjoint trees connecting S_x,y,z we find. If V(A) 6=V(G), by Lemmas 3.4 and 3.5, we can assume that A₀ =∅, (V(G)\V(A)) ⊆X and (V(A₁)\S_x,y,z)⊆X, where X=U, V,orW. Since A₀ =∅,A₁ 6=∅ by the maximality ofA.

Case 1. X=U.

Since (V(G)\V(A)) ⊆ U and (V(A₁)\S_x,y,z) ⊆ U, any vertex v ∈ (V ∪W)\S_x,y,z is in some tree T ∈A₂.

Claim: If there is a tree T ∈ A₂ with vertex set S_x,y,z ∪ {v, w}, where v ∈ V \S_x,y,z and w∈W \S_x,y,z, then|V(G)\V(A)|= 1.

Proof. By contradiction, suppose that there are two vertices in V(G)\V(A), say u⁰, u⁰⁰. Let T₁ and T₂ be two trees inA₂ with vertex setsS_x,y,z∪ {v, u⁰} and S_x,y,z∪ {u⁰⁰, w}, respectively.

Since forT⁰ ∈A\ {T},T⁰ does not containu⁰, u⁰⁰, v, wnor the edges incident with them,T_i and T⁰ are edge-disjoint, and V(T_i)∩V(T⁰) = S_x,y,z for i = 1,2. Clearly, E(T₁)∩E(T₂) = ∅ and V(T₁)∩V(T₂) =S_x,y,z. LetA⁰ =A\ {T} ∪ {T₁, T₂}. It is easy to see thatA⁰is a set of internally disjoint trees connectingS_x,y,z. But |A⁰|=|A|+ 1, contradicting to the maximality of A.

Since |W \S_x,y,z|=b−z≥b−x=|U \S_x,y,z|>|U \V(A₁)|, there must be a tree T ∈A₂ with vertex set S_x,y,z∪ {v, w}, wherev ∈V \S_x,y,z and w∈W \S_x,y,z. So |V(G)\V(A)|= 1.

Denote the vertex in V(G)\V(A) by u⁰. Take a tree T₁ ∈ A₁ with vertex set S_x,y,z∪ {u⁰⁰}, where u⁰⁰ ∈ U \S_x,y,z. Let T₂ and T₃ be two trees in A₂ with vertex sets S_x,y,z ∪ {v, u⁰} and S_x,y,z∪ {u⁰⁰, w}, respectively. Since for T⁰ ∈A\ {T, T₁},T⁰ does not containu⁰, u⁰⁰, v, w nor the edges incident with them, T_i and T⁰ are edge-disjoint, and V(T_i)∩V(T⁰) =S_x,y,z for i= 2,3.

Clearly, E(T₃)∩E(T₂) = ∅ and V(T₃)∩V(T₂) = S_x,y,z. Let A⁰ = A\ {T, T₁} ∪ {T₃, T₂}. It is easy to see thatA⁰ is a set of internally disjoint trees connectingS_x,y,z. Since|A⁰|=|A|,A⁰ is a maximum set of internally disjoint trees connecting S_x,y,z, such thatV(A⁰) =V(G).

(9)

Case 2. X=V.

The proof is similar to that of Case 1.

Case 3. X=W.

In this case, since |W \S_x,y,z| = b−z ≥ b−y ≥ b−x = |U \S_x,y,z|, it seems that it is possible that there is no tree T ∈ A₂ with vertex set S_x,y,z∪ {v, u}, where v ∈ V \S_x,y,z and u ∈ U \S_x,y,z, and hence any vertex v ∈ (V ∪U)\S_x,y,z is in some tree T ∈ A₂ with vertex set S_x,y,z ∪ {v, w}, where w ∈ W \V(A₁). But actually this is impossible. This is because it implies that b−x+b−y < b−z, namely, b+z < x+y. Since (V(A₁)\S_x,y,z) ⊆ W,

|A₁|=|V(A₁)\S_x,y,z|< b−z < b+z < x+y andE(A)∩E(G[U_x∪V_y]) =∅. Now|A₁|< x+y implies that for every vertex w_i ∈ S_x,y,z, i = 1, . . . , z, there is at least one unused edge in E(G[S_x,y,z]) incident with w_i. These edges together with the edges in E(G[U_x∪V_y] will form a tree in A₀, which is internally disjoint with all trees in A, contradicting to the maximality of A. So there must be a tree T ∈ A₂ with vertex set S_x,y,z∪ {v, u}, where v ∈ V \S_x,y,z and u ∈U\S_x,y,z. Similar to the proof of Case 1, we can transform A to A⁰, which is a maximum set of internally disjoint trees connectingS_x,y,z, such that V(A⁰) =V(G).

So, we can assume that if A is a maximum set of internally disjoint trees connecting S_x,y,z, thenV(A) =V(G).

Lemma 3.7 Let A ⊂ A₀∪ A₁ ∪ A₂ be a maximum set of internally disjoint trees connecting S_x,y,z, and A = A₀ ∪A₁ ∪A₂. If A₀ 6= ∅ and A₂ 6= ∅, then we can find a maximum set A⁰ = A⁰₀ ∪A⁰₁ ∪A⁰₂ of internally disjoint trees connecting S_x,y,z, such that |A⁰₀| = |A₀| −1,

|A⁰₁|=|A₁|+ 2, and |A⁰₂|=|A₂| −1.

Proof. LetT be a tree inA₂with vertex setS_x,y,z∪{u, v}, whereu∈U\S_x,y,zandv∈V\S_x,y,z. Let T₁ be a tree in A₀. We want to transform T and T₁ to two trees T₂, T₃ ∈ A₁ with vertex setsS_x,y,z∪ {u}and S_x,y,z∪ {v}respectively. InT₂, every vertex inU_xmust be incident with an edge inE(T₁). In T₃, every vertex in V_y must be incident with an edge inE(T₁). And all these edges must be distinct. To do this, let the vertices inW_z be in Layer 0. Let the vertices having distance i to W_z in T₁ be in Layer i. Every vertex in U_x∪V_y is in some Layer i, 1 ≤ i ≤ k, sinceT₁ is connected. For each vertexu⁰ ∈U_x∪V_y, assume thatu⁰ is in Layeri. Take one edge connectingu⁰ with some vertex in Layeri−1. There must be such an edge by our construction.

According to our choices of edges, these edges are all distinct. So T₂ and T₃ are edge-disjoint and V(T₃)∩V(T₂) =S_x,y,z. Since for T⁰ ∈A\ {T, T₁},T⁰ does not contain u, v nor the edges incident with them and T⁰ does not contain the edges of T₁, T_i and T⁰ are edge-disjoint, and V(T_i)∩V(T⁰) =S_x,y,z fori= 2,3. LetA⁰ =A\ {T, T₁} ∪ {T₃, T₂}. It is easy to see thatA⁰ is a set of internally disjoint trees connecting S_x,y,z. Since |A⁰₀| =|A₀| −1, |A⁰₁|=|A₁|+ 2, and

|A⁰₂| = |A₂| −1, |A⁰|= |A|. Thus A⁰ is a maximum set of internally disjoint trees connecting S_x,y,z we want to find.

So, we can assume that if A is a maximum set of internally disjoint trees connecting S_x,y,z, then either A₀ orA₂ is empty.

From the above lemmas, we can form our principle in finding the maximum set of internally disjoint trees connectingS_x,y,z. First we find as many trees inA₁ as possible. IfV(A₁)6=V(G), we then find as many trees inA₂ as possible; else if V(A₁) =V(G), we then find as many trees inA₀ as possible. So the final maximum set Aof internally disjoint trees connecting S_x,y,z is of the formA₀∪A₁ orA₁∪A₂. IfA=A₀∪A₁, then every vertexv∈V(G)\S_x,y,z is contained in some tree T ∈A₁ with vertex setS_x,y,z∪ {v}. Since |V(G)\S_x,y,z|= 3b−k, there are (3b−k) trees in A₁. So |A| ≥ 3b−k. If A = A₁ ∪A₂, every tree in A must contain one vertex in