Packing k-edge Trees in Graphs of Restricted Vertex Degrees

a r X i v :m a t h /0610384v 1 [m a t h .C O ] 11 O c t 2006PACKING k -EDGE TREES IN GRAPHS OF RESTRICTED VERTEX DEGREES

Alexander K.Kelmans

University of Puerto Rico,San Juan,Puerto Rico Rutgers University,New Brunswick,New Jersey Abstract Let G s r denote the set of graphs with each vertex of degree at least r and at most s ,v (G )the number of vertices,and τk (G )the maximum number of disjoint k -edge trees in G .In this paper we show that (a 1)if G ∈G s 2and s ≥4,then τ2(G )≥v (G )/(s +1),(a 2)if G ∈G 32and G has no 5-vertex components,then τ2(G )≥v (G )/4,(a 3)if G ∈G s 1and G has no k -vertex component,where k ≥2and s ≥3,then τk (G )≥(v (G )?k )/(sk ?k +1),and (a 4)the above bounds are attained for in?nitely many connected graphs.Our proofs provide polynomial time algorithms for ?nding the corresponding packings in a graph.Keywords :subgraph packing,2-edge and k -edge paths,k -edge trees,poly-nomial time approximation algorithms.1Introduction We consider simple undirected graphs.All notions on graphs that are not de?ned here can be found in [1,3].Given a graph G and a set F of subgraphs of G ,an F -packing of G is a subgraph of G whose components are members of F .The F -packing problem is that of ?nding an F -packing having the maximum number of vertices.Various F -packing problems have extensively been studied by many authors for di?erent families F (e.g.[2,4–7,12–17]).It is not surprising that F -packing problem turns out to be NP -hard for most of

the families F .Surprisingly the problem can be solved in polynomial time for some non-trivial families.For example,Edmonds (see [17])showed that a classical matching problem can be solved in polynomial time.It is also known that the problem of packing stars of at least one and at most k edges is polynomially solvable even if the stars,we pack,are required to be induced [7,9].On the other hand,the problem of ?nding in G the maximum number of disjoint subgraphs,isomorphic to a given connected graph H of at least three vertices,is NP -hard [5].The problem remains NP -hard for cubic graphs if H is a path having at least two edges [11].

In this paper we consider the H -packing problem when H is a tree and,in particular,when H =Λ,a path of two edges.Although the Λ-packing problem is NP -hard,i.e.possibly intractable in general,this problem turns out to be tractable for some natural classes of graphs.Here are some examples of such results.

Let v(G)denote the number of vertices of a graph G andτk(G)denote the maximum number of disjoint k-edge trees in G.We also putτ2(G)=λ(G).

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3 (which is called a claw).

A block

B of a graph G is called an end-block of G if B has exactly one vertex adjacent to a vertex in G?B.

Obviouslyλ(G)≤?v(G)/3?.

1.1[6]Suppose that G is a connected claw-free graph having at most two end-blocks (in particular,a2-connected claw-free graph).Thenλ(G)=?v(G)/3?.

Let G?be the graph obtained from a cubic graph by“replacing”every vertex by

a triangle.From1.1we have,in particular,for cubic graphs:

1.2[6]Suppose that G is a connected cubic graph having at most two end-blocks(in particular,a2-connected graph).Thenλ(G?)=?v(G?)/3?.

Let eb(G)denote the number of end-blocks of G.The previous theorem follows from the following more general result.

1.3[6]Suppose that G is a simple connected claw-free graph and eb(G)≥

2.Then λ(G)≥?(v(G)?eb(G)+2)/3?,and this lower bound is sharp.

1.4[12]Let T be a tree on t vertices and let?>0.Suppose that G is a d-regular graph

on n vertices and d≥128t3

?2).Then G contains at least(1??)n/t vertex disjoint

copies of T.In particular,if G n is a d n-regular graph on n vertices and d n→∞when n→∞,then G n contains at least(1?o(1))n/t(and,obviously,at most n/t)disjoint trees isomorphic to T.

1.5[13]Let G be a cubic graph.Thenλ(G)≥v(G)/4.

Let G s r denote the set of graphs with each vertex of degree at least r and at most s.Our main question onΛ-packings is:

How many disjoint2-edge paths must an n-vertex graph G from G s2have?

In1.6and1.7we give corresponding lower bounds on the numbers in question. We also show(see1.8)that these bounds are tight.

1.6Suppose that G∈G32and G has no5-vertex components.Thenλ(G)≥v(G)/4.

Obviously1.5follows from1.6because if G is a cubic graph then G∈G32and G has no5-vertex components.

1.7Let G∈G s

2

,s≥4.Thenλ(G)≥v(G)/(s+1).

We give constructions(see Section4)that allow us to prove the following:

1.8There are in?nitely many connected graphs for which the bounds in1.6and1.7 are attained.Moreover,for every integer k,such that1≤k≤s,there are in?nitely many subdivisions of k-regular graphs for which the bounds in1.6and1.7are attained.

We also consider a special case of the F-packing problem when F is the set of all connected subgraphs of G having k edges.Let T k denote the set of all trees having k edges.Obviously this problem is equivalent to the T k-packing problem,the problem of?nding in a graph the maximum number of disjoint trees of k edges.Notice that Theorem1.4provides a similar asymptotic result for the T k-packing problem.Our question on T k-packings is:

How many disjoint k-edge trees must an n-vertex graph G from G s1have?

In1.9we give a lower bound on the number in question.We also show(see1.10) that these bounds are tight.

Our main result on the T k-packing problem are the following:

and G has no k-vertex 1.9Let s and k be integers,s≥3,k≥2.Suppose that G∈G s

1

component.Thenτk(G)≥(v(G)?k)/(sk?k+1).

One of the constructions in Section4allows to prove:

1.10There are in?nitely many connected graphs for which the bound in1.9is at-tained.

Our proofs provide polynomial time algorithms for?nding the corresponding pack-ings in graphs from G s r.Thus these algorithms are polynomial approximation algo-rithms for the corresponding problems.

The results of this paper were presented at the Workshop“Graph Partitions”in DIMACS,Rutgers University,in July,2000(see also[10]).

2Main notions,notation and simple observations Let G be a simple graph.We use the following notation and notions:

V=V(G)and E=E(G)are the sets of vertices and edges of a graph G,respectively, v(G)=|V(G)|and e(G)=|E(G)|,

if x∈V(G),then d(x,G)=d(x)is the degree of x in G,

xP y is a path with the end-vertices x and y,

an F-packing of G is a subgraph of G whose components are members of F,

aΛ-packing is a subgraph of G whose components are2-edge paths in G,

λ(G)is the maximum number of vertex disjoint2-paths in G,

τk(G)is the maximum number of disjoint k-edge trees in G,where k≥1,and so λ(G)=τ2(G).

A path-thread in a graph G is a maximal path P in G such that each vertex of degree two in P is also of degree two in G.A cycle-thread in G is a cycle C in G such that each vertex of C,except for one,is of degree two in G.A thread is either a path-thread or a cycle-thread.

A block of a connected graph G is a maximal connected subgraph H of G such that

H?v is connected for every v∈V(H).A block B of a graph G is called an end-block of G if B has exactly one vertex adjacent to a vertex in G?B.

A leaf of a graph G is either a vertex of degree one or an end-block of at least two edges in G.An H-leaf is a leaf isomorphic to a graph H.If k is an integer,then a k-leaf is a leaf having k vertices.

Let,as above,G s r denote the set of graphs with each vertex of degree at least r and at most s.

Let F32denote the set of graphs such that

(a1)d(x,G)∈{2,3}for every vertex x of G and

(a2)G has no5-vertex components.

Given a class of graphs A,a graph G is called A-mininimal if G∈A and G?e∈A for every e∈E(G).Obviously G s r-minimal and F32-minimal graphs exist.

It is easy to see the following.

2.1Let G be a graph.

(c1)If G∈F32(G∈G s r),then G has an F32-minimal(respectively,G s r-minimal)span-ning subgraph F andλ(G)≥λ(F).

(c2)A graph G is F32-minimal if and only if each edge of G is incident to either a vertex of degree two in G or to a vertex of a5-leaf of G.

,Q be a leaf of G.Then Q∈F32,the boundary vertex q of Q is 2.2Let G∈F3

2

of degree two in Q,and there is a(unique)path-thread xT y=S(Q)in G such that x=q∈V(Q)and y∈V(G?Q).

If Q is a leaf of a graph G∈F32,then S(Q)is called the stem of the leaf Q.

Let`Q be the graph obtained from Q∪S(Q)by removing the vertex of degree one.

3Graph reductions

Our proving strategy is to establish various properties of a minimum counterexam-ple,and?nally conclude that it cannot exist.At various stages in this process,we will need some operations that reduce a minimum counterexample to a smaller one providing a contradiction.In this section we present such reductions.

3.1Let G be a graph,xT y be a thread of G,where possibly x=y,T′=T?{x,y}, and G′=G?T′(see Figure??).Let s≥3be an integer.

(a1)If s≥4and e(T)≥4,thenλ(G′)≥v(G′)/(s+1)?λ(G)≥v(G)/(s+1).

(a2)If s=3and v(T′)∈{3k,3k+1},where k≥1is an integer,then

λ(G′)≥v(G′)/4?λ(G)≥v(G)/4.

Proof Clearly v(G)=v(G′)+v(T′)andλ(G)≥λ(G′)+?v(T′)/3?.Nowλ(G′)≥v(G′)/(s+1)?λ(G)≥v(G′)/(s+1)+?v(T′)/3?=v(G)/(s+1)+γs(T′)where γs(T′)=?v(T′)/3??v(T′)/(s+1).Since e(T)≥4,clearly v(T′)≥3.

Suppose that s≥4.Then obviouslyγs(T′)≥0.

Now suppose that s=3.If v(T′)=3k,thenγ3(T′)=k?3k/4=t/4.If v(T′)=3k+1,thenγ3(T′)=k?(3k+1)/4=(k?1)/4≥0.Since k≥1,in both casesλ(G)≥v(G)/(s+1).

3.2Let G be a graph,xT y be a thread of G,and T′=T?{x,y}.Let G′be obtained from G?T′by adding a new vertex z and two new edges edge xz and yz(see Figure ??).Suppose that v(T′)=3k+2,where k≥1is an integer.Thenλ(G′)≥v(G′)/4?λ(G)≥v(G)/

4.

Proof Clearly v(G)=v(G′)+v(T′)?1.Since v(T′)=3k+2and k≥1,clearly λ(T′)=k.Let P′be a maximumΛ-packing in G′,and soλ(G′)=|P′|.Let xst be a subpath of T.

(p1)Suppose that{xz,yz}∩E(P′)=?.Thenλ(G)≥λ(G′)+λ(T′)=λ(G′)+k. Nowλ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+k=(v(G)?v(T′)+1)/4+k=v(G)/4+ k?(3k+1)/4=v(G)/4+(k?1)/4≥v(G)/4.

(p2)Suppose that|{xz,yz}∩E(P′)|=1,say rxz is a2-edge path in P′for some r∈V(G?T′).Let P′′be a maximumΛ-packing in T′′=T′?s,and P=P′∪P′′?rxz∪rxs. Then P is aΛ-packing in G,and soλ(G)≥|P|=|P′|+|P′′|=λ(G′)+λ(T′′).Since v(T′′)=v(T′)?1=3k+1,we haveλ(T′′)=k.Therefore,as in(p1),λ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+k≥v(G)/4.

(p3)Now suppose that xz,yz∈E(P′),i.e.xz′y is a2-edge path in P′.Let P′′be a(unique)maximumΛ-packing in T′′=T′?{s,t}.Let P=P′∪P′′?xzy∪xst. Then P is aΛ-packing in G,and soλ(G)≥|P|=|P′|+|P′′|=λ(G′)+λ(T′′). Since v(T′′)=v(T′)?2=3k,we haveλ(T′′)=k.Therefore again,as in(p1),λ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+k≥v(G)/4.

3.3Let e∈E(G).Suppose that G?e=A∪B,where A and B are disjoint subgraphs of G and v(A)≥3.Suppose also thatλ(A)=?v(A)/3?.Let G′=B.Then the implicationλ(G′)≥v(G′)/(s+1)?λ(G)≥v(G)/(s+1)holds for s=3provided v(A)=5,as well as for every integer s≥

4.

Proof Clearly v(G)=v(A)+v(B)andλ(G)≥λ(`A)+λ(B).Thereforeλ(B)≥v(B)/(s+1)??v(A)/3?+λ(G)≥v(B)/(s+1).We claim that if s≥3,then ?v(A)/3?≥v(A)/(s+1).This is obviously true for s≥4and also true for s=3 because v(A)=5.Thereforeλ(G)≥v(A)/(s+1)+v(B)/(s+1)≥v(G)/(s+1).

3.4Let w=ab∈E(G)be a thread of G,a=b,d(a,G)=d(b,G)=3,G?w=A∪B, where A and B are disjoint subgraphs of G,a∈V(A),and b∈V(B).Let x i T i b, i=1,2,be the two di?erent threads of G distinct from awb,bz i∈E(T i),`A=G?(B?b) (i.e.`A=A∪awb and A′=`A∪{bz1,bz2}.Suppose that v(`A)=6andλ(`A)=2. (a1)If e(T i)=2for i=1,2,then let x i T i b=x i z i b(see Figure??).

(a1.1)If x1=x2,then let G′=G?A′.

(a1.2)If x1=x2,then let G′be obtained from G?A′by adding a new edge u=z1z2 (see Figure??).

(a2)If e(T1)=3,e(T2)=2,then let x1T1b=x1y1z1b,x2T2b=x2z2b.

(a2.1)If x1=x2,then let G′be obtained from G?A′by adding a new edge u=y1x2 (see Figure??).

(a2.2)If x1=x2,then let G′be obtained from G?A′by adding a new edge u=y1z2 (see Figure??).

(a3)If e(T1)=3,e(T2)=3,then let x1T1b=x1y1z1b,x2T2b=x2y2z2b and G′be obtained from G?A′by adding a new edge u=y1y2(see Figure??).

Then G∈G32?G′∈G32andλ(G′)≥v(G′)/4?λ(G)≥v(G)/4.

?G′∈G32.We prove the second claim.Since Proof It is easy to check that G∈G3

2

v(`A)=6andλ(`A)=2,clearly v(A′)=8andλ(A′)=2,respectively.Let P′be a maximumΛ-packing in G′.

(p1)Suppose that u∈E(G′)?u∈E(P′).In particular,our assumption holds in case(a1.1).In cases(a1.2)and(a2.2),u belongs to a triangle-leaf of G′.Hence there exists a maximumΛ-packing in G′avoiding u.Therefore we can assume that P′avoids u,and so our assumption holds in these cases as well.In cases(a1.1)and(a2.2) v(G)=v(G′)+v(A′)andλ(G)≥λ(G′)+λ(A′).Thereforeλ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+λ(A′)=(v(G)?8)/4+2=v(G)/4.In case(a1.2)v(G)=v(G′)+v(`A) andλ(G)≥λ(G′)+λ(`A).Thereforeλ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+λ(A′)= (v(G)?6)/4+2>v(G)/4.

(p2)Suppose that u∈E(G′),u∈E(P′),e(T1)=3,e(T2)=2,and x1=x2,and so (a2.1)holds and u=y1x2.

(p2.1)Suppose that x1y1∈E(P′),say y1x2c2∈P′,where c2∈V(G′?{x2,y1}).Let P1 be a maximumΛ-packing of A1=(A′?z2)∪y1z1and P=(P′∪P1?y1x2c2)∪z2x2c2. Then P is aΛ-packing of G,|P|=|P′|+|P1|,andλ(G)≥|P|=λ(G′)+λ(A1). Obviouslyλ(A1)=λ(A′)=2.Therefore,as in(p1),λ(G′)≥v(G′)/4?v(G)/4.

(p2.2)Suppose that x1y1∈E(P′),i.e.x1y1x2∈P′.Let P2be a maximumΛ-packing of A2=A′?z1and P=(P′∪P1∪x1y1z1)?x1y1x2.Then P is aΛ-packing of G, |P|=|P′|+|P2|,andλ(G)≥|P|=λ(G′)+λ(A2).Obviouslyλ(A2)=2.Therefore, as in(p1),λ(G′)≥v(G′)/4?v(G)/4.

(p3)Suppose that u∈E(P′),e(T1)=3,e(T2)=3,and so(a3)holds and u=y1y2. Because of symmetry,we can assume that x1y1y2∈P′.Let P3be a maximumΛ-packing of A3=(A′?z1)∪y2z2and P=(P′∪P3?x1y1y2)∪x1y1z1.Then P is aΛ-packing of G,|P|=|P′|+|P3|,andλ(G)≥|P|=λ(G′)+λ(A3).Obviously λ(A3)=2.Therefore,as in(p1),λ(G′)≥v(G′)/4?v(G)/4.

3.5Let G be a graph,a∈V(G),d(a,G)=d,{aT i x i:i∈I}be the set of threads of

G with a common vertex a,and S a=∪{T i?x i:i∈I}(possibly x i=x j when i=j). Let s≥3be an integer and suppose that3≤d≤s.Suppose that e(T i)≤3for every i∈I.Let I=I1∪I2∪I3be a partition of I such that I1=I and(1)i∈I1implies T i is a triangle,(2)i∈I2implies T i is a2-edge path,say x i z i a,and(3)i∈I3implies T i is a3-edge path,say x i y i z i a.

Let T k={aT i x i:i∈I k}and X k={x∈V(G):aT x∈T k},i.e.X k is the set of end-vertices of threads in T k that are di?erent from a,k∈{2,3}.Let t x be the number

of threads in T 2ending at x .Let X ′2={x ∈X 2\X 3:t x ≥2,d (x )=t x +1}.If x ∈X ′2,

then let L x be a (unique )thread which ends at x and is not in T ,l x =e (L x ),and L ′x be the subpath of L x which ends at x and has l x vertices.Suppose that each l x ≤3and if |I 3|is odd,then I 2=?.Let G ′be obtained from G as follows.

(a 1)Suppose that I 3is even.Let S ′a =(S a ?∪{y i :i ∈I 3})∪(∪{L ′x :x ∈X ′2}).

Partition I 3into pairs {i,i ′}and put G ′=(G ∪{y i y i ′:i ∈I 3})?S ′a

(see Figure ??).(a 2)Suppose that I 3is odd,and so I 3=?.Choose r ∈I 3and j ∈I 2and partition I 3?r into pairs {i,i ′}.(Since by our assumption,I 3is odd,I 2=?,and so such j exists.)

(a 2.1)If x r =x j ,then let S ′a =(S a ?(∪{y i :i ∈I 3?r }∪z j ))∪(∪{L ′x :x ∈X ′2?x j })

and G ′=G ∪x r z j ∪{y i y i ′:i ∈I 3?r }?S ′a (see Figure ??).

(a 2.2)If x r =x j ,then let S ′a =(S a ?(∪{y i :i ∈I 3}∪z j ))(∪{L ′x :x ∈X ′2?x j })and

G ′=G ∪y r z j ∪{y i y i ′:i ∈I 3?r }?S ′a

(see Figure ??).(We say that G ′is obtained from G by a reduction of the vertex star S a .)

Then G ∈G s 2?G ′∈G s 2and λ(G ′)≥v (G ′)/(s +1)?λ(G )≥v (G )/(s +1).

Proof We can assume that G is a connected graph.It is easy to check that

G ∈G s 2?G ′∈G s 2.We prove the second claim.Let P ′be a maximum Λ-packing of

G ′,and so |P ′|=λ(G ′).Obviously,v (G )=v (G ′)+v (S ′a ).Let |X ′2|=d ′.Obviously d ′≤d ≤s .

(p1)Consider case (a 1)with I 3=?,and so |I 3|is even.Then v (G )=v (G ′)+v (S ′a )and v (S ′a )=d +1+ {l x :x ∈X ′2

}.Let P be obtained from P ′as follows.If edge y i y i ′belongs to a 2-edge path L ′∈P ′with the center,say y k in {y i ,y i ′},then replace L ′in P ′by the 2-edge path L =(L ′?y k ′)∪{z k ,y k z k },where {k,k ′}={i,i ′}.

Then |P|=|P ′|=λ(G ′).Let S ′′a =S ′a ?V (P ).Then P is a Λ-packing in G and

λ(G )≥|P|+λ(S ′′a ).and λ(S ′′a )=1+d ′.Since d ′≤d ≤s and each L x ≤3,we have

v (S ′a )≤s +1+3d ′.Since s ≥3,clearly λ(S ′a )=1+d ′>1+3d ′/(s +1)≥v (S ′a )/(s +1).Therefore λ(G ′)≥v (G ′)/(s +1)?λ(G )≥λ(G ′)+λ(S ′′a )≥v (G ′)/(s +1)+v (S ′a )/(s +

1)=v (G )/(s +1).

(p2)Consider case (a 2.1),i.e.I 3is odd and x r =x j .Then v (G )=v (G ′)+v (S ′a )and v (S ′a )=d +1+ {l x :x ∈X ′2}.Let P be obtained from P ′as follows.If edge y i y i ′in

G ′,where i =r ,belongs to a 2-edge path L ′∈P ′with the center,say y k y k in {y i ,y i ′},then,as in (p1),replace L ′in P ′by the 2-edge path L =(L ′?y k ′)∪{z k ,y k z j },where {k,k ′}={i,i ′}.If edge x r z j in G ′belongs to a 2-edge path P ′∈P ′and P ′=x r z j x j (P ′=x r z j x j ),then replace P ′in P ′by 2-edge path P =(P ′?z j )∪{y r ,x r y r }(respectively,by 2-edge path P =x r y r z r ).Then |P|=|P ′|=λ(G ′).Let S ′′a =S ′a ?V (P ).Then P is a Λ-packing in G and λ(G )≥|P|+λ(S ′′a ).As in

(p1),λ(S ′′a )=1+d ′≥v (S ′a )/(s +1).Therefore λ(G ′)≥v (G ′)/(s +1)?λ(G )≥

λ(G ′)+λ(S ′′a )≥v (G ′)/(s +1)+v (S ′a )/(s +1)=v (G )/(s +1).

(p3)Consider case (a 2.2),i.e.I 3is odd and x r =x j .Then v (G )=v (G ′)+v (S ′a )and v (S ′a )=d + {l x :x ∈X ′2}.Since y r z j belongs to a triangle-bock in G ′,there

exists a maximum Λ-packing P ′in G ′that avoids y r z j .Let P be obtained from P ′as follows.If edge y i y i ′in G ′,where i =r ,belongs to a 2-edge path L ′∈P ′with the center,say y k in {y i ,y i ′},then,as in (p1),replace L ′in P ′by the 2-edge path

L=(L′?y k′)∪{z k,y k z j},where{k,k′}={i,i′}.Then P is aΛ-packing in G and|P|=|P′|=λ(G′).Let S′′a=S′a?V(P).Thenλ(G)≥|P|+λ(S′′a).It is easy to see,thatλ(S′′a)=1+d′and v(S′a)≤d+3d′≤s+1+3d′.Hence,as in (p1),λ(S′′a)=1+d′≥v(S′a)/(s+1).Thereforeλ(G′)≥v(G′)/(s+1)?λ(G)≥λ(G′)+λ(S′′a)≥v(G′)/(s+1)+v(S′a)/(s+1)=v(G)/(s+1).

3.6Let a∈V(G),d(a,G)=3,aT i x i be the three threads ending at a.Suppose that x j belongs to a5-leaf X j,e(T j)=1for j=1,2.Let G′be obtained from G?(X1∪X2?{x1,x2})by adding a new edge x1x2(see Figure??).Thenλ(G′)≥v(G′)/4?λ(G)≥v(G)/

4.

Proof Let X=X1∪X2?{x1,x2}.Obviously,v(G)=v(G′)+v(X),v(X)=8,λ(X)=2,andλ(G)≥λ(G′)+λ(X).Thereforeλ(G′)≥v(G′)/4?λ(G)≥v(G′)/4+λ(X)=(v(G)?8)/4+2=v(G)/4. 4Constructions of extremal graphs

In this section we give constructions providing in?nitely many connected graphs for which the bounds in1.6,1.7,and1.9are attained.

Let s≥1be an integer and T s denote the set of trees T such that every non-leaf vertex in T has degree s.Obviously T∈T1?v(T)=2.

Let k≥1be an integer and T k be obtained from T∈T s by subdividing each non-dangling edge of T with k vertices and each dangling edge with k?1vertices.Let T s,k={T k:T∈T s}.

AΛk-packing N is a subgraph of G such that every component of N is a k-edge path.Letλk(G)denote the maximum number of disjoint k-edge paths in G.Obviously λ1(G)=τ1(G)is the size of a maximum matching in G,λ(G)=λ2(G)=τ2(G),and λk(G)≤τk(G).

The following result provides in?nitely many connected graphs for which the bound in1.9is attained.

4.1Let k≥1and s≥1be integers and T∈T s.Thenλk(T k)=τk(T k)=(v(T k)?k)/(sk?k+1).

Proof We prove our claim onλk(T k)by induction on v(T).The proof onτk(T k) is similar.If s=1,then v(T)=2,and so our claim is true.So let s≥2.Then v(T)≥s+1.If v(T)=s+1,then T=K1,s+1,and so our claim is true.So let v(T)>s+1.Let L x denote the set of leaves in T adjacent to a vertex x.Since T∈T s and v(T)>s+1,clearly T has a vertex z with|L z|=s?1.Let T′=T?L z. Then v(T′)=v(T)?(s?1)and T′∈T s.Let Y z be the subgraph of T induced by z∪L z.Clearly Y z is isomorphic to K1,s?1.Let Y z k be obtained from Y z by subdi-viding each edge with k?1vertices.Then T′k=T k?Y z k.Obviouslyλk(Y z k)=1, v(T k)=v(T′k)+v(Y z k),v(Y z k)=sk?k+1,and T k has a maximumΛk-packing P that contains exactly one k-edge path from Y z k.Henceλk(T k)=λk(T′k)+λk(Y z k).Since

v(T′)

(v(T k)?k)/(sk?k+1).

Let Y denote the graph obtained from three disjoint cycles A i of?ve vertices by adding a new vertex a and three edges{aa1,aa2,aa3},where a i∈V(A i),i=1,2,3.It is easy to see thatλ(Y)=v(Y)/4=4.Here is a more general construction of extremal graphs which shows,in particular,that there are in?nitely many connected graphs for which the bounds in1.6and in1.7are attained.

4.2Let H be a graph with possible loops and parallel edges such that each vertex of

H is of degree at least three and at most s.Let H k be a graph obtained from H by subdividing every edge with exactly k≥1vertices.Thenλk(H k)=τk(H k)=v(H). Moreover,λ(H2)=v(H)≥v(H2)/(s+1)and the equality holds if and only if H is an s-regular graph.

Proof Obviouslyλk(H k)≤τk(H k).Let P be aΛk-packing in H k.Then each k-edge tree in P contains a vertex from V(H).Thereforeλk(H)≤τk(H k)≤v(H).We can assume that H is connected.Let T be a spanning tree of H.Obviously there is an edge e=xy∈E(H)?E(T).Let D=T∪e and D x be the directed graph obtained from D by directing each edge of T?D towards x and by directing e from x to y.For z∈D x,let p(z)denote the edge in D x with the tail z.Clearly p:V(D x)→E(D x) is a bijection.Let¨D be obtained from D by subdividing each edge of D with exactly k vertices.Then every edge e in D is replaced in¨D by a thread which we denote by L(e).Let p k(z)denote the k-edge path in thread L(p(z)containing z.We can assume that¨D?H k.Let P={p k(z):z∈V(D x)}.Then clearly P is aΛk-packing in¨D,and therefore in H k,and|P|=v(T)=v(H).Thereforeλk(H)=τk(H k)=|P|=v(H).

Obviously,2e(H)≤sv(H)and v(H2)=v(H)+2e(H)≤(s+1)v(H).Therefore λ(H2)=v(H)≥v(H2)/(s+1)and the equality holds if and only if H is an s-regular graph. 5Proof of Theorem1.6

First we will establish some properties of a hypothetical minimum counterexample to theorem1.6.We will use these properties to proof theorem1.6by showing that no counterexamples exist.

In all claims below,except for1.6,we assume that G is a connected graph satisfying the following conditions:

(a1)G is an F32-minimal graph,

(a2)λ(G)

(a3)G has the minimum number of vertices among all graphs satisfying(a1)and(a2).

5.1Let aT b be a thread of G.If neither a nor b belongs to a5-leaf,then e(T)∈{2,3}. Proof(uses3.1and3.2).Suppose,on the contrary,that e(T)∈{2,3}.Obviously e(T)≥1.If T has exactly one edge u,then G?u∈F32,and so G is not F32-minimal,

a contradiction.Therefore we have exactly one of the following two cases:

(c1)e(T)∈{3k+1,3k+2},where k≥1and

(c2)e(T)=3k,where k≥2.

(p1)Suppose that e(T)∈{3k+1,3k+2},where k≥1.Let,as in3.1,G′= G?(T?{a,b}).Since G∈F32and neither a nor b belongs to a5-leaf,we have G′∈F32.Clearly v(G′)

(p2)Now suppose that e(T)=3k,where k≥2.Let G′be the graph de?ned in3.2. Since G∈F32,obviously G′∈F32.Clearly v(G′)

5.2G has no5-leaves.

Proof(uses3.3,3.4,3.6,and5.1).Suppose,on the contrary,that G has a5-leaf X1.Let aT1x1be the stem of X1,i.e.a(unique)thread in G such that x1∈V(X1).If a belongs to a5-leaf or a cycle-leaf A,then G=A∪T1∪X1and G has a Hamiltonian path. Henceλ(G)=?v(G)/3?.Obviously v(G)>5.Thereforeλ(G)=?v(G)/3?≥v(G)/4, a contradiction.So we assume that a belongs to neither a5-leaf nor a cycle-leaf.

(p1)Suppose that e(T1)≥2.Let`X1=X1∪(T1?a)and,as in3.3,G′=G?`X1.Then λ(`X1)=?v(`X1/3?.Since G∈F32and a belongs to no5-leaf,we have G′∈F32.Clearly v(G′)

(p2)Now suppose that e(T1)=1.Let aT2x2and aT3x3be the threads containing a and distinct from aT1x1.Since a belongs to no cycle-leaf,clearly T2=T3.If x i belongs to no5-leaf,then by5.1,e(T i)∈{2,3}.

(p2.1)Suppose that neither x2no x3belongs to a5-leaf.Then e(T i)∈{2,3}for i=1,2.Let G′be the graph de?ned in3.4,where`A=X1∪T1.Then v(`A)=6and λ((`A)=2.By3.4,G∈F32implies G′∈F32.Clearly v(G′)

(p2.2)Now suppose that x i belongs to a5-leaf X i for some i∈{2,3},say for i=2. Then by the above arguments on e(T1),we can assume that e(T2)=1.Let G′be the graph de?ned in3.6.Then G∈F32implies G′∈F32.Clearly v(G′)

5.3Every path-thread in G has exactly three edges.

Proof(uses3.5,5.1,and5.2).By5.2,G has no5-leaves.Let aT1x1be a path-thread in G.By5.1,e(T1)∈{2,3}.Suppose,on the contrary,that e(T1)=2.If each end-vertex of T belongs to a cycle-leaf,then obviouslyλ(G)≥v(G)/4.Therefore we can assume that one end-vertex,say a,of T1belongs to no cycle-leaf.

Let aT1x1,aT2x2,and aT3x3be the three di?erent path-threads ending at a.Since G has no5-leaves,by5.1,e(T2)∈{2,3}and e(T3)∈{2,3}.Let x i x′i,aa i∈E(T i)for i∈{1,2,3},and so a i=x′i if and only if e(T i)=2.

If x1=x2=x3=x,then G consists of three threads with common end-vertices a and x.Since G∈F32,we have v(G)≥6.Therefore v(G)∈{6,7}.Obviously λ(G)=2=?v(G)/4?,a contradiction.Therefore we assume that{x1,x2,x3}has at least two di?erent vertices.Thus we have(up to symmetry)the following three cases: (c1)x1=x2=x3=x,(c2)x=x1=x2=x3,and(c3)all x i’s are di?erent.

Let G′be a graph obtained from G by a reduction of the vertex star S a(see3.5). Namely(we remind that in this particular case),G′is obtained from G as follows.

Consider case(c1),i.e.x1=x2=x3=x.If{e(T2),e((T3)}={2,3},say{e(T2)=2 and e(T3)=3,then G′=(G?a1aa3)∪x′2x′3.If e(T2)=e(T3)=2,then G′= G?(T1∪T2∪T3∪Z?x1),where Z is the set of inner vertices of the thread containing x and distinct from T i,i∈{2,3}.If{e(T2)=e((T3)}=3,then G′=(G?{a,a1,a2,a3})∪x′2x′3.

Consider case(c2),i.e.x=x1=x2=x3.If e(T2)=2and e(T3)=3,then we can put G′=(G∪a′1x3)?a′2aa′3x′3.If e(T2)=3and e(T2)=3,then we can put G′=(G∪x′1x′2)?a′2aa′3.If e(T2)=e(T3)=2,then G′=G?(T1∪T2∪T3∪Z?x1), where Z is the set of inner vertices of the thread containing x and distinct from T i, i∈{1,2}.If{e(T2)=e((T3)}=3,then G′=(G∪x′2x′3)?(T1∪T3?{x1,x3}).

Consider case(c3),i.e.all x i’s are di?erent.If e(T2)=e(T3)=2,then G′= G?{a,a1,a2,a3}.If{e(T2),e(T3)}={2,3},say e(T2)=2and e(T3)=3,then we can put G′=(G?{a,a1,a3,x′3}∪x′2x3.If e(T2)=e(T3)=3,then G′=(G?{a,a1,a2,a3})∪x′2x′3.

By3.5,G∈F32?G32?G′∈G32.Since5.2,G has no5-leaves,we have G′∈F32. Clearly v(G′)

5.4Every cycle-leaf of G is a triangle.

Proof(uses3.3,5.2,and5.3).Let A be a cycle-leaf of G and aT b be the stem of A with a∈V(A).

Suppose that v(`A)=5.Let,as in3.3,G′=G?`A.Obviouslyλ(`A)=?v(`A)/3?.By 5.2,G has no5-leaves.Therefore G∈F3

implies G′∈F32.Clearly v(G′)

2

the minimality of G,λ(G′)≥v(G′)/4.Then by3.3,λ(G)≥v(G)/4,a contradiction.

Now suppose that v(`A)=5,i.e.v(A)+e(T)=6.By5.3,e(T)=3.Therefore v(A)=3.

Now we are ready to prove

1.6Let G∈F3

.Thenλ(G)≥v(G)/4.

2

Proof(uses2.1,4.2,5.3,and5.4).Suppose,on the contrary,that our claim is not true.Obviously,a triangle is the minimum graph in F32and our claim is true for a triangle.Let G be a vertex minimum counterexample.By2.1,we can assume that G is F32-minimal.In other words,G is a graph such that(a1)G be an F32-minimal graph, (a2)λ(G)

The construction in4.2provides in?nitely many2-connected graphs(moreover, subdivisions of3-connected graphs)G in F32such thatλ(G)=v(G)/4.

6Proof of Theorem1.7

In all claims below,except for1.7,we assume that G is a connected graph satisfying the following conditions:

(a1)G is an G s2-minimal graph,s≥4,

(a2)λ(G)

(a3)G has the minimum number of vertices among all graphs satisfying(a1)and(a2).

6.1Let xT y be a thread of G,where possibly x=y.Then e(T)∈{2,3}.

Proof(uses3.1).Suppose,on the contrary,that e(T)∈{2,3}.Obviously e(T)≥1.If T has exactly one edge u,then G?u∈G s2,and so G is not G s2-minimal,a contradiction.Therefore e(T)≥4.Let,as in3.1,G′=G?(T?{x,y}).Obviously G∈G s2implies G′∈G s2.Clearly v(G′)

6.2Every thread of G has exactly three edges.

Proof(uses3.5and6.1).If T is a cycle-thread of G,then by6.1,T is a triangle, and so e(T)=3.So let us consider a path-thread a1T1x1.By6.1,e(T1)∈{2,3}.

Suppose,on the contrary,that e(T1)=2.Let{T i:i∈{1,...,k}}be the set of threads of G with a common end-vertex a.Let G′be a graph de?ned in3.5.Then by G∈G s2implies G′∈G s2.Clearly v(G′)

Now we are ready to prove

and s≥4.Thenλ(G)≥v(G)/(s+1).

1.7Let G∈G s

2

Proof(uses2.1,4.2,and6.2).Suppose,on the contrary,that our claim is not true.Obviously,a triangle is the minimum graph in G s2and our claim is true for a triangle.Let G be a vertex minimum counterexample.By2.1,we can assume that G is G s2-minimal.In other words,G is a graph such that(a1)G be an G s2-minimal graph, (a2)λ(G)

The construction in4.2provides in?nitely many2-connected graphs(moreover, subdivisions of3-connected graphs)G in G s2such thatλ(G)=v(G)/(s+1).

7Proof of Theorem1.9

A subtree

B of a tree is called a branch of T if either B=T or T?B is also a tree.If B=T,then let r(B)be the vertex of B adjacent to a vertex in T?B.We call r(B)the root of the branch B.

Let,as above,τk(G)denote the maximum number of disjoint k-edge trees in G.

,and v(T)≥k+1.Then T 7.1Let s≥3and k≥1be integers,T a tree,T∈G s

1

has a branch B such that v(B)≤(s?1)k+1andτk(B)=1.

Proof We prove our claim by induction on v(T).If v(T)=k+1,then our claim is obviously true.Therefore let v(T)>k+1.A branch B of a tree T∈G s1is called k-good if v(B)≤(s?1)k+1andτk(B)=1.Let x be a leaf of T and T′=T?x. Clearly T′is a tree,T′∈G s1,and v(T′)

Suppose that v(X′)

Now suppose that v(X′)=k.Then X is a k-edge subtree of T,X is a branch of T,v(X)≤v(B′)(s?1)k+1,andτk(X)=1.Therefore X is a k-good branch in T.

Now we are ready to prove

1.9Let s≥3and k≥1be integers,G∈G s1,and G has no k-vertex components.Then τk(G)≥(v(G)?k)/(sk?k+1).

.We can assume that G is connected and v(G)≥k. Proof(uses7.1).Let G∈G s

1

Since G has no k-vertex component,v(G)≥k+1.Let T be a spanning tree of G. Clearly T∈G s1andλk(G)≥λk(T).Therefore it is su?cient to proof our claim for every tree T in G s1.

We prove our claim for trees by induction on v(T).If v(T)=k+1,then our claim is obviously true.So let v(T)>k+1.By7.1,T has a branch B such that v(B)≤(s?1)k+1andτk(B)=1.Let T′=T?B.Clearly T′∈G s1,v(T′)

The construction in4.1provides in?nitely many trees T in G s1such thatτk(G)= (v(G)?k)/(sk?k+1).

References

[1]J.A.Bondy and U.S.R.Murty,Graph theory with applications,North Holland,

Amsterdam,1976.

[2]G.Cornu′e jols and D.Hartvigsen,An extension of matching theory,https://www.sodocs.net/doc/0d16032081.html,bin.

Theory B40(1986)285–296.

[3]R.Diestel,Graph Theory,Springer,2005.

[4]Y.Egawa,M.Kano,A.Kelmans,Star partitions of graphs,Journal of Graph

Theory,25No.3,(1997)185–190.

[5]P.Hell and D.Kirkpatrick,On the complexity of general graph factor problems,

SIAM https://www.sodocs.net/doc/0d16032081.html,put.12,(1983)601–609.

[6]A.Kaneko,A.Kelmans,T.Nishimura,On packing3–vertex paths in a graph,J.

Graph Theory36(2001)175–197.

[7]A.Kelmans,Packing induced stars in a graph,RUTCOR Research Report26-94,

Rutgers University(1994)1–25.

[8]A.Kelmans,On a duality theorem for packing induced stars in a graph,RUTCOR

Research Report43-96,Rutgers University(1996)1–6.

[9]A.Kelmans,Optimal packing of induced stars in a graph,Discrete Mathematics,

173,(1997)97–127.

[10]A.Kelmans,Packing trees in graphs,DIMACS Technical Report2000–44,Rutgers

University(2000).

[11]A.Kelmans,Packing P k in a cubic graph is NP–hard for k≥3,manuscript.

[12]A.Kelmans,D.Mubayi,and B.Sudakov,Packing trees in a regular graph DI-

MACS Research Report2000–22,Rutgers University(2000)1–10and Electronic Journal of Conbinatorics,vol.8(1)(2001).

[13]A.Kelmans and D.Mubayi,How many disjoint2–edge paths must a cubic graph

have?,DIMACS Technical Report2000–23,Rutgers University(2000)1–18and Journal of Graph Theory,45(2004)57–79.

[14]https://www.sodocs.net/doc/0d16032081.html,s Vergnas,An extension of Tutte’s1–Factor theorem,Discrete Mathematics

23(1978),241-255.

[15]M.Loebl and S.Poljak,Subgraph packing–A survey,In Topics in Combinatorics

and Graph Theory:Essays in Honour of Gerhard Ringel,Phisica Verlag,Wursburg, 1990,491–503.

[16]M.Loebl and S.Poljak,On matroids induced by packing subgraphs,https://www.sodocs.net/doc/0d16032081.html,bin.

Theory B44(1988)338–354.

[17]L.Lovasz and M.Plummer,Matching Theory,North-Holland,Amsterdam,1986.

详解雅思听力section1考点及解题技巧(三)

详解雅思听力section1考点及解题技巧（三）有过雅思考试经历的考生都知道雅思听力考试的四个section中，就题目的难度、考察的背景信息及录音的速度而言，section 1可以说是难度较低的一部分，然而，纵观考题卷，我们却经常发现section 1的正确率有时却不尽人意。下面为大家详解雅思听力section1考点及解题技巧，希望对大家的雅思听力备考有帮助。 二、解题思路 Section 1中的解题思路可划分为2个环节，分别是：角色分工、信息陷阱。 1、角色分工 从section 1是一个conversation的文体上看，10道题的角色分工是很明显的。根据角色的不同，我们分为信息提问者和信息提供者。从卷面上我们不难发现， (1)10道题都是由信息提供者即回答问题的人提供，比如：Cambridge 7 Test 1 S1; (2)其中有2-4道题是由信息提问者提供，比如：Cambridge 5 Test 2 S1。 2、信息陷阱 (1)信息提问者所提供的答案多数为“陷阱”。 我们对section 1的题目做好角色分工后，就可以根据角色来做题。因为大部分的题目是由信息提供者提供，因此考生在听题的时候，可以不理会信息提问者给出的答案。 (2)信息提供者提供答案的过程中，信息随时会发生转变。 下面我们通过剑桥5 Test 2 Section 1的部分题目来讲解这2个环节。 Q2 two forms of ID e.g. driving license………………..

Q6 Computers can be booked up to……….. hours in advance. 我们先来看一下这两道题的录音： LIBRARIAN: We also need two documents for ID, so a driving license would be fine. MAN: I have got that and what else? A credit card?(陷阱之一) LIBRARIAN: No, it needs to have your address on it.(陷阱之二) MAN: Shall I bring a bank statement,(正确答案) would that do? LIBRARIAN: That’ll be fine.(给予肯定) MAN: Do I have to book in advance for them? LIBRARIAN: Oh, yes, it’s advisable. Most people tend to book 24(陷阱之一) hours in advance although sometimes you can get one with only 6(陷阱之二) hours’notice. However,(语气转折) the earliest you can book a computer is 48(正确答案) hours before you need it. 从录音中可以看出MAN是信息提问者，LIBRARIAN是信息提供者。Q2是由信息提问者提供答案，最终由信息提供者来确定正确答案，而Q6是直接由信息提供者提供答案，但信息不断更换—最终however后给出了正确答案。 以上就是详解雅思听力section1考点及解题技巧的内容，希望对大家的雅思备考有帮助。最后，预祝大家在雅思考试中取得满意的成绩。

The way常见用法

The way 的用法 Ⅰ常见用法： 1)the way+ that 2)the way + in which（最为正式的用法） 3)the way + 省略（最为自然的用法） 举例：I like the way in which he talks. I like the way that he talks. I like the way he talks. Ⅱ习惯用法： 在当代美国英语中，the way用作为副词的对格，“the way+ 从句”实际上相当于一个状语从句来修饰整个句子。 1)The way =as I am talking to you just the way I’d talk to my own child. He did not do it the way his friends did. Most fruits are naturally sweet and we can eat them just the way they are—all we have to do is to clean and peel them. 2）The way= according to the way/ judging from the way The way you answer the question, you are an excellent student. The way most people look at you, you’d think trash man is a monster. 3）The way =how/ how much No one can imagine the way he missed her. 4）The way =because

雅思口语考试必备基础知识及应试技巧

雅思口语考试必备基础知识及应试技巧 一、在日常口语练习中应注意哪些问题，如何进行提高? 首先大家要明白，口语考试的目的，绝不仅仅是通过考试，而是增强口语交流的能力，毕竟大家以后都要出国学习的。那么在没有英语环境的条件下，如何给自己创造环境?我本人正在做的，也是我的学生们正在做的，是每天半小时的英语新闻，口语考试不仅仅是说话，更要听懂对方在说什么，所以你听懂了老外说的，你熟悉了对方的语调，对自己的口语听力，有着直接的帮助，对于阅读和写作，长远看来也是很有益的。就想9月7日刚刚结束的雅思考试A类大作文，讲述的是nuclear power—核能。很多学生望而却步，不知道如何下笔，但如果有听英语新闻的考生，会发现要写这样的作文并不是件很困难的事情。这也就不难理解，为什么考官曾经说过，不要求考生的知识面很深，但要广。 平时除了听新闻，更要多加强一些雅思口语考试环境的模拟。往往有很多考生平时练习和积累很好，但一到考场上就出现怯场，连平时能听懂的、会说也不会了，这严重影响了考试成绩。对此，我建议考生平时一定要多，加强一些话题讨论的练习，最好报个培训班，可以得到老师的更多在技巧、应试中的真传。对于口语学习，小马过河是不错的选择，有针对雅思的单独的口语精炼，老师大多是国外回来的，纯真的口音有助于口语水平的提升，对于相对基础较差的考生来，

可以考虑先上基础的剑桥课程打底子，即使第一次考试不过，还可以继续通过网络课程的进一步学习，准备下次考试。

二、考前考生应该注意些什么? 很多考生在雅思考试口语考试之前会更加努力地去复习，导致紧张情绪增加，其实考前应该心情放松，心态平和，考试才能正常发挥水平。因为考试首先考验的是大家的心态。所以，建议考生考前做到一下几点： 1.提前一周调整生物钟，习惯早睡早起。争取把最佳状态调整到上午时间段，而非继续做夜猫子。 2.千万不要题海战术，每天一套题只能让你力不从心。即使无力完成复习目标，也不要苛求，不必给自己太大压力。 3.、坚持给自己营造英文环境。坚持每天听一段听力，像平时一样，念一阵英文，还可以适当看一看美剧，毕竟考场上的PART1也是首先展现你交际能力的机会，如果发音准确，表达地道，那么你就先拔头筹了。 4.摆正心态，相信只要付出必有收获。 三、考生在雅思口语考试部分的得分普遍在5分左右，真正的高分是凤毛麟角的。

The way的用法及其含义(二)

The way的用法及其含义（二） 二、the way在句中的语法作用 the way在句中可以作主语、宾语或表语： 1.作主语 The way you are doing it is completely crazy.你这个干法简直发疯。 The way she puts on that accent really irritates me. 她故意操那种口音的样子实在令我恼火。The way she behaved towards him was utterly ruthless. 她对待他真是无情至极。 Words are important, but the way a person stands, folds his or her arms or moves his or her hands can also give us information about his or her feelings. 言语固然重要,但人的站姿,抱臂的方式和手势也回告诉我们他(她)的情感。 2.作宾语 I hate the way she stared at me.我讨厌她盯我看的样子。 We like the way that her hair hangs down.我们喜欢她的头发笔直地垂下来。 You could tell she was foreign by the way she was dressed. 从她的穿著就可以看出她是外国人。 She could not hide her amusement at the way he was dancing. 她见他跳舞的姿势，忍俊不禁。 3.作表语 This is the way the accident happened.这就是事故如何发生的。 Believe it or not, that's the way it is. 信不信由你, 反正事情就是这样。 That's the way I look at it, too. 我也是这么想。 That was the way minority nationalities were treated in old China. 那就是少数民族在旧中

雅思写作应试技巧 答案

第二節經濟原則 1. Some people are strongly against space research because they think it is an extravagant and wasteful project for developing countries. 2. Many people are struggling at the poverty line, lacking food and shelter. Why not use the limited public funds to help them alleviate poverty? 3. The primary responsibility of a government is to help its people eliminate poverty, disease and illiteracy. 4. The development of tourism creates many job opportunities and great amounts of foreign currency. 5. Play ing computer games all day lavishes parents’ hard-earned money. 6. Art funding is a luxurious practice to many developing countries. 7. Improving people’s welfare is the government’s obligation. 8. The construction of stadiums and theaters squanders the go vernment’s tight budget. 9. It is a dissipation of taxpayers’ money for the government to subsidize artists and musicians. 10. It is a luxurious dream for children in the poverty-stricken area to receive formal education. 11. Net-surfing is a costly hobby. 12. Preservation of endangered species is a great economic burden on the developing nations. 13. Hosting the Olympic Games can increase the government revenue and create more employment. 14. A private car is a luxury to many destitute families. 15. It is a laudable endeavor to help children in the impoverished area to have access to formal education. 16. Sending children to study abroad is a heavy financial burden on many families. 17. The development of space exploration lavishes the limited public funds. 18. College students’ taking part-time jobs helps ease the financial burden of their parents. 19. It is a great economic burden for a government with a tight budget to subsidize artists and drama companies, which lavishes taxpayers’ money. 20. Legalization of gambling can bring the government a great amount of foreign currency and at the same time create a considerable number of employment opportunities.

(完整版)the的用法

定冠词the的用法： 定冠词the与指示代词this ,that同源,有“那(这)个”的意思,但较弱,可以和一个名词连用,来表示某个或某些特定的人或东西. (1)特指双方都明白的人或物 Take the medicine.把药吃了. (2)上文提到过的人或事 He bought a house.他买了幢房子. I've been to the house.我去过那幢房子. (3)指世界上独一无二的事物 the sun ,the sky ,the moon, the earth (4)单数名词连用表示一类事物 the dollar 美元 the fox 狐狸 或与形容词或分词连用,表示一类人 the rich 富人 the living 生者 (5)用在序数词和形容词最高级,及形容词等前面 Where do you live?你住在哪? I live on the second floor.我住在二楼. That's the very thing I've been looking for.那正是我要找的东西. (6)与复数名词连用,指整个群体 They are the teachers of this school.(指全体教师) They are teachers of this school.(指部分教师) (7)表示所有,相当于物主代词,用在表示身体部位的名词前 She caught me by the arm.她抓住了我的手臂. (8)用在某些有普通名词构成的国家名称,机关团体,阶级等专有名词前 the People's Republic of China 中华人民共和国 the United States 美国 (9)用在表示乐器的名词前 She plays the piano.她会弹钢琴. (10)用在姓氏的复数名词之前,表示一家人 the Greens 格林一家人(或格林夫妇) (11)用在惯用语中 in the day, in the morning... the day before yesterday, the next morning... in the sky... in the dark... in the end... on the whole, by the way...

雅思口语考试技巧

口语考试如果希望取得高分(比如7分以上)，不但要有一定的口语水平，还要来点“旁门左道”。依据我的经验，口语考试成绩=个人真实的口语水平x现场表现系数x考官认可系数。这三部分中，口语水平短时间内很难有大的提高，虽然完全可以通过充分的准备从而“脱胎换骨”。考官是否认可不能由你把握，但是与你的现场表现直接相关。所以，如果想要在口语考试中拿到高分，最能控制也是最立竿见影的就是你的现场表现。一句话：你要影响考官。 一、雅思口语考试三大破绽 口语考试并非"无机可乘",相反,它的主观性决定了它与生俱来的不准 确性。从两次口语取得8分的经历中,我总结出雅思口语考试有以下破绽,从而使考生能用于影响考官: 1 口语考试的成绩与你的真实水平是正相关的，但不是成正比的。也就是说，在你毫无准备的情况下，它能够测出你属于哪一个档次的，比如说，5-6分是一个中级档次，7-8分是一个高级档次。但是在同一个档次内部，到底是5分还是6分，7分还是8分，完全取决于两个人的主观博弈-你和考官。 2 口语考试的生杀大权掌握在考官手中，所以要“攻城为下，攻心为上”。我的口号是“要把考官当人看”,而不是机器或者大牲口(虽然你心里是这么想的)。口语考试考察的是考生的"沟通"能力,而非单纯的"口语"能力。所以,如果你在考试开始前没有礼貌地和考官打招呼,没有尊重地问问考官的名字,说话的时候表 情冷漠,没有笑容,光目呆滞,总是保持一个声调，使人感到乏味，离开考场时忘了对考官说"再见",总之就是没有给予考官对正常人应有的礼貌和尊重时,你是 休想得高分的。

3 “多算胜，少算不胜”。我们不能打无把握之仗，而要在考试前积极备战，从而使雅思口语考试的科学性在你的成绩上体现的微乎其微。因为口语考试采用的是题库制，所以所有的题目都能从网上找到“机经”。你完全可以做到有的放矢的备考。一旦你有了充分的准备，即使自认为口语水平一般的同学,通过一定的技术处理,完全有可能在口语考试中作到"点石成金",从而取得7分以上的成绩。 二、现场表现系数的四大要素 口语考试要有以下几个要素才能得高分:自信,反应,语音和表情。这就是我说的“现场表现系数”。 1 自信。你有面对考官的自信吗？比如,你是否会很轻松地反问考官:"What can I call you?"从而给考官的笫一印象就是:这个人肯定口语不错,因为其它考生都不敢和我这样!口语考试不同于一般的和鬼子聊天,而是你和一个考官在一间“阴森可怖”的小黑屋里面，你看着他，他看着你。你无权保持沉默，并且你所说的每一句话都将成为承堂证供，因为你面前还摆着一个录音机。你曾有的自信就在你还没有进入口语考场之前的焦急等待中彻底土崩瓦解了。那你就完了，因为你下面的口语考试就会出现技术变形。自信从何而来？准备。如果你对即将考到的题目烂熟于胸，你会不自信吗？如果你已经拥有了大量和鬼子练口语的经历，发现他们无非就是一群来中国“潇洒走一回”的流浪汉，你会不自信吗？所以，试问那些一考口语就紧张的同学，你们有谁在考试之前做到了以上这两点呢？ 2 反应。如果你希望对口语考试中的所有问题都有所准备，这是mission impossible。所以要对没有准备过的问题做出敏锐地反应。我第二次考8分的时候被问到一个问题：“Are physical exercises popular in China？”

“the way+从句”结构的意义及用法

“tｈｅwａｙ+从句”结构的意义及用法 首先让我们来看下面这个句子: Ｒead the foｌloｗｉnｇpassagｅａnd talkａbout ｉt wi ｔh your classmaｔes．Try tｏｔeｌl whaｔyｏu thiｎk ｏf Tom aｎd ｏｆｔhe ｗay the chiｌｄrenｔrｅated ｈim. 在这个句子中，ｔhe waｙ是先行词,后面是省略了关系副词that或in whｉch的定语从句。 下面我们将叙述“the ｗaｙ+从句”结构的用法。 1.tｈe wａy之后，引导定语从句的关系词是tｈat而不是hoｗ,因此，<<现代英语惯用法词典＞＞中所给出的下面两个句子是错误的：Ｔhｉs is ｔｈeｗayｈowｉtｈａppened. This is the way how he ａlwａｙs treats me. 2．在正式语体中,thaｔ可被in which所代替;在非正式语体中，ｔhat则往往省略。由此我们得到theｗay后接定语从句时的三种模式：1) tｈe ｗaｙ＋ｔhａt-从句２）the way +ｉn whiｃh－从句3) the ｗay +从句 例如：Ｔｈe way(in whiｃh ，thａt) ｔhｅｓｅｃomｒade ｓloｏｋａｔｐrobｌems is wrong．这些同志看问题的方法

不对。 Ｔｈｅｗａy(that ,ｉn ｗhiｃh)yoｕ’ｒe doinｇit is comple ｔeｌy crａzy.你这么个干法,简直发疯。 Wｅａdmiｒｅd him for thｅｗay ｉｎｗhｉch he fａｃeｓdiｆficultieｓ． Waｌlａｃe ａｎd Ｄarwiｎｇreed ｏn the way ｉｎwhi ｃh ｄｉfｆｅrｅnt forms ｏf life had ｂegｕn.华莱士和达尔文对不同类型的生物是如何起源的持相同的观点。 Thｉs is ｔｈe ｗaｙ（tｈａｔ) hｅdｉd it. I lｉkeｄｔhe waｙ(ｔhat) ｓｈeｏｒganized ｔhe ｍeetｉng． 3.theｗay(tｈat)有时可以与hｏw(作“如何”解）通用。例如： That’s tｈe ｗaｙ(tｈaｔ) shｅspoke. = Tｈat’s how shｅspoke.

雅思口语的应试技巧和答题思路总结

雅思口语的应试技巧和答题思路总结 雅思口语是雅思考试的重点和难点，由于是采用一对一的真人对话形式，我们在 实际的考场上不仅需要一些英语方面的技巧，也需要一些对话交流方面的技巧。 这篇文章就将雅思口语在备考时的技巧和考场上的技巧都汇总了一下。 一、技巧总结 雅思口语考试技巧一：提前准备适合自己的口语高分词汇 在备考的时候，准备一些常用的7分雅思词汇和雅思技巧，在适当的时候脱口而出，会给你的考试增光添色，同时要在考前的练习过程中，掌握好paraphrase的方法，因为在雅思考试的过程中，由于紧张或者是本身词汇的匮乏，在自己不会的单词上面 会卡壳，而雅思口语是相对比较灵活的，在这种情况下，需要我们用其他的话去替代 那个卡壳的点，这样你的雅思口语就会顺畅、自然。 雅思口语考试技巧二：灵活应对雅思口语考试中的话题 雅思考试中的话题有很多，疑难话题是大家拿到雅思口语满分的最大障碍，当你 在雅思考试的时候，遇到的题目是从来没有见过的，或者是自己比较生疏的话题，需 要你灵活转换，但是当你无法做到灵活转化的时候，那就需要说一个最容易而且最能 说出内容的话题。 雅思口语考试技巧三：充分利用考试中笔记记录 雅思口语考试中的一张纸，就是第二部分开始的时候，考官会给你一张纸和一支笔，让你在思考的时候可以做一些笔记，有些考生觉得做笔记没什么意义，因为做完 了之后，说的时候还是和笔记大相径庭，这说明考生在下面练习的时候没有很好的掌 握通过看笔记说英语的习惯，因此在考场上才会觉得笔记没太大作用。 雅思口语考试技巧四：调节心理状态，不畏惧，不胆怯 雅思考试注重的是语言的应用性，因此在考场中的状态和心态对你的考试起到了 举足轻重的作用，大部分的考生都没有参加过这样的口语考试，因此在考前对考试存 在一种惧怕感，总是担心自己见到老外之后，可能会说的都会变成不会说的，这就是 一种考试障碍，所以需要大家把自己的心态放平稳，一定要把雅思口语考试当成是一 个和考官的谈话，是和一个陌生人的谈话，仅此而已。把自己想说的，能说的，全都 表达出来。 二、两个拓展雅思口语答题思路的方法

way 用法

表示“方式”、“方法”，注意以下用法： 1.表示用某种方法或按某种方式，通常用介词in(此介词有时可省略)。如： Do it (in) your own way. 按你自己的方法做吧。 Please do not talk (in) that way. 请不要那样说。 2.表示做某事的方式或方法，其后可接不定式或of doing sth。 如： It’s the best way of studying [to study] English. 这是学习英语的最好方法。 There are different ways to do [of doing] it. 做这事有不同的办法。 3.其后通常可直接跟一个定语从句(不用任何引导词)，也可跟由that 或in which 引导的定语从句，但是其后的从句不能由how 来引导。如： 我不喜欢他说话的态度。 正：I don’t like the way he spoke. 正：I don’t like the way that he spoke. 正：I don’t like the way in which he spoke. 误：I don’t like the way how he spoke. 4.注意以下各句the way 的用法： That’s the way (=how) he spoke. 那就是他说话的方式。 Nobody else loves you the way(=as) I do. 没有人像我这样爱你。 The way (=According as) you are studying now, you won’tmake much progress. 根据你现在学习情况来看，你不会有多大的进步。 2007年陕西省高考英语中有这样一道单项填空题： ——I think he is taking an active part insocial work. ——I agree with you_____. A、in a way B、on the way C、by the way D、in the way 此题答案选A。要想弄清为什么选A，而不选其他几项，则要弄清选项中含way的四个短语的不同意义和用法，下面我们就对此作一归纳和小结。 一、in a way的用法 表示：在一定程度上，从某方面说。如： In a way he was right.在某种程度上他是对的。注：in a way也可说成in one way。 二、on the way的用法 1、表示：即将来(去)，就要来(去)。如： Spring is on the way.春天快到了。 I'd better be on my way soon.我最好还是快点儿走。 Radio forecasts said a sixth-grade wind was on the way.无线电预报说将有六级大风。 2、表示：在路上，在行进中。如： He stopped for breakfast on the way.他中途停下吃早点。 We had some good laughs on the way.我们在路上好好笑了一阵子。 3、表示：(婴儿)尚未出生。如： She has two children with another one on the way.她有两个孩子，现在还怀着一个。 She's got five children，and another one is on the way.她已经有5个孩子了，另一个又快生了。 三、by the way的用法

雅思听力：例解填空题型应试技巧

雅思听力：例解填空题型应试技巧。 以剑桥六第59页的4道填句子题为例，原题如下： MARKETING ASSIGNMENT 21.For their assignment，the students must investigate one part of the _________. 22.The method the students must use to collect data is_________. 23.In total，the students must interview_______people.

24.Jack thinks the music preferences of _________listeners are similar. 当面对这样一组题目的时候，首先应该做的是读懂题，划关键词特别是空前后关键词，预测并标记。就是说在读懂句子意思的同时要划出关键词来，那么那些词是关键词呢?一般来讲包括有句子的主语谓语宾语，专有名词，术语以及年代和数字。其余的根据做题人自己的感觉也可以略有添减。但是空前后的关键词则是同学们比较容易忽略而以后必须要注意的。这个划关键词和预测，标记都是同步进行的。比如21题，主要是讲学生们必须研究什么东西的一部分，关键词可以划下the students ，investigate ，one part of the 这几个，其中one part of the 又属于空前后的词汇那么就更要划下并且关注了。这个题不好看出内容来，只能大致猜测是要填学生们要研究的主题，但是是填个名词性的东西这一点应该是明确的，那么就可以在空格里标出n 来提醒自己这个地方等下要填名词。按照这种方法，上面四个题在读完题后应该成为下面的样子 MARKETING ASSIGNMENT

雅思托福应试技巧讲座心得

雅思托福应试技巧讲座心得 今天晚上，我去听了关于雅思托福应试技巧的讲座，受益匪浅，更加明确了自己的目标和大学英语的学习方法。 老师从什么是雅思，什么是托福开始讲起，带我们走进了英语的世界。她为我们消除了对雅思托福的恐惧心理，盲从心理。老师告诉我们，雅思托福，听上去很洋气的两个名词，其实并不可怕，只要认真学习，用心学习，我们也能做到。 打好基础。老师告诉我们，学好英语，最关键的一点是达到一定的词汇量。高中需要3500词汇量，英语四级需要4000词汇量，雅思需要8000词汇量。一切的一切都说明了，要学好英语必须保证一定的词汇量。老师又强调了要反复记忆与练习，学习单词需要我们的耐心，需要我们的坚持。总之，学好英语一定要打好基础，扩大自己的词汇量。 注重日常练习。英语听力能力的提高在于每日的积累。老师告诉我们要做一个有心人，她向我们推荐了几款app，还告诉了我们一些英语学习网站，让我们自己在网上进行自主学习。尤其是“scientific American 60 second”这个app。每天只需要抽出一分钟来学习，就能很好地提高自己的英语听力水平。 功夫不负有心人。英语作文水平的提高在于平时词汇与语法的积累。老师给我们展示了一篇雅思成绩为7分的作文。考生运用了各种

语法，句型，而且运用了许多词形变换。而且从文中可以看出考生为了准备考试积累了许多专业词汇。老师告诉我们，要想在众多考生中脱颖而出，就必须能够灵活地运用新颖的词汇，熟练的运用各种句型。而且要多积累专业词汇，这能够给改卷老师留下一个好印象。功夫不负有心人，我们要在平常做好积累。 多阅读。老师推荐了好几本杂志，与雅思官方出的书，老师说，有好多考试内容摘自这些文章，要多读这些杂志与参考书，还可以提高自己的英语阅读水平。 在大学四年，我要制定学习英语的规划，努力提高自己的英语水平，铺垫出自己的成功之路。

The way的用法及其含义(一)

The way的用法及其含义（一） 有这样一个句子：In 1770 the room was completed the way she wanted. 1770年，这间琥珀屋按照她的要求完成了。 the way在句中的语法作用是什么？其意义如何？在阅读时，学生经常会碰到一些含有the way 的句子，如：No one knows the way he invented the machine. He did not do the experiment the way his teacher told him.等等。他们对the way 的用法和含义比较模糊。在这几个句子中，the way之后的部分都是定语从句。第一句的意思是，“没人知道他是怎样发明这台机器的。”the way的意思相当于how；第二句的意思是，“他没有按照老师说的那样做实验。”the way 的意思相当于as。在In 1770 the room was completed the way she wanted.这句话中，the way也是as的含义。随着现代英语的发展，the way的用法已越来越普遍了。下面，我们从the way的语法作用和意义等方面做一考查和分析： 一、the way作先行词，后接定语从句 以下3种表达都是正确的。例如：“我喜欢她笑的样子。” 1. the way+ in which +从句 I like the way in which she smiles. 2. the way+ that +从句 I like the way that she smiles. 3. the way + 从句(省略了in which或that) I like the way she smiles. 又如：“火灾如何发生的，有好几种说法。” 1. There were several theories about the way in which the fire started. 2. There were several theories about the way that the fire started.

way 的用法

way 的用法 【语境展示】 1. Now I’ll show you how to do the experiment in a different way. 下面我来演示如何用一种不同的方法做这个实验。 2. The teacher had a strange way to make his classes lively and interesting. 这位老师有种奇怪的办法让他的课生动有趣。 3. Can you tell me the best way of working out this problem? 你能告诉我算出这道题的最好方法吗？ 4. I don’t know the way (that / in which) he helped her out. 我不知道他用什么方法帮助她摆脱困境的。 5. The way (that / which) he talked about to solve the problem was difficult to understand. 他所谈到的解决这个问题的方法难以理解。 6. I don’t like the way that / which is being widely used for saving water. 我不喜欢这种正在被广泛使用的节水方法。 7. They did not do it the way we do now. 他们以前的做法和我们现在不一样。 【归纳总结】 ●way作“方法，方式”讲时，如表示“以……方式”，前面常加介词in。如例1； ●way作“方法，方式”讲时，其后可接不定式to do sth.，也可接of doing sth. 作定语，表示做某事的方法。如例2，例3；

雅思听力流程图解题方法及步骤

雅思听力流程图解题方法及 步骤 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

参加了或者围观了9月24日雅思听力考试的同学们，无一例外的都被section2出现的一篇关于咖啡豆的流程图虐的体无完肤，考生回忆说只听到满耳朵的bean…bean…bean… 究其原因，最根本的是考生普遍在备考时，并没有重视流程图的练习，且剑桥系列中流程图又鲜有出现，导致同学们对于此种体型并没有很明确的认知，对于答题思路以及考点易出点的概念都比较模糊。 一般情况下，流程图常见出现的位置为section2或者section3,题目数量一般4～6道题，答题节奏感是制胜关键。 流程图一般分为填空类流程图和匹配类流程图。 填写类以剑桥8test4 section3的流程图为例：

填写类流程图的一般答题步骤为： 1, 预判空格词性 本题中第27题词性为名词，并且和revision构成从属关系。拓展从属关系考点，当题干结构为A for/from/of B时，音频中可能为BA结构，反之亦然。28和30题，可数名次单数 29题，名词。 2, 划出空格前后关联实词 因为一般题干上的关键词会在音频中先行，提示音频即将进入此道题目的答案句。 3, 音频中逐个定位卷面信息 即使没有出题的地方（如本题第一句话find some past papers）也要在音频中定位，防止跟丢。答案句往往跟在卷面信息所在句子之后。 4, 提取答案句中符合预判的词性，准确拼写。 答案句： 27－then you can sort out your revision priorities. 28－but that isn’t enough in itself. You also need a timetable. 29－so if you break down your revision into small tasks 30－and as I revise each topic I write a single paragraph. 由答案句以及其他填空类流程图答题可知，题目间的过渡词或词组，是把握答题节奏感的关键，因此同学们要对此类词汇敏感，如：

必看：雅思考试听力第四部分应试技巧

必看：雅思考试听力第四部分应试技巧 听力Section4的应试技巧 Section4是公认的雅思听力考试最难的部分，大部分考生在平时的训练中积累了较强的恐惧心理。这与Section4的常考话题和出题方式有关。在该部分考试中，考生会听到一段长独白，通常是由一名大学教授或是专家给出一个话题，话题的内容比较广泛，会涉及环境，文化，健康等一系列比较专业的问题。在语言和句型的使用上，也会出现一些考生不太熟悉的文法，这些都在一定程度上会造成考生理解上的障碍。但是，虽然话题比较专业，所问的问题都不涉及专业知识，也不考察考生的专业词汇。所以该部分的目的不是考验你是否掌握某个专业知识，而是测试你的听力理解能力以及对细节信息的把握。 Section4的题型及应试技巧 纵观05-06年的考题，Section4的大部分考题都是以填空题为主，有时为Summary填空，有时为填表题，所以对写的要求很高。因此，考生要做的第一步准备工作就是提高单词拼写的速度和准确性。尤其要重视对以前考试中常考场景的场景词汇的总结。经验告诉我们，场景词汇反复出现的比率很大。 大多数考生在完成这一部分的时候觉得时间很紧，因此我们建议考生在一拿到试卷的时候就注意听力考试的时间控制。尤其在

Section1做题之前，几乎有2分钟的时间审题，这段时间里，学生除了可以把Section1的题目做详细的审题外，建议把后三个Section 的场景和题型也浏览一遍。 在Section3结束后到Section4做题之前，会有近1分钟的时间可以预览题目。首先要看的就是考题指示中的字数限制，一般是NOMORETHANTHREEWORDS，但是有时也会是NOMORETHANTWOWORDS甚至是ONLYONEWORD，一定要看清再作答，否则即使答案的内容正确，字数超标也不给分的。然后，要快速预览试题，找出题目中的关键字，根据自己的语法知识确定答案的词性，同时，根据常识判断答案可能包含的大致内容。另外，如果碰到table题，可以依照顺序原则，根据题号出现的顺序来判断试题是按照横向还是纵向发展的，并且按照表格中已有的信息来判断空格的格式和内容，如可以判断数字、时间、金额和大小写信息。想在半分钟的时间内把试题都预测完，就一定要加快预览的速度，这可以通过一些快速阅读的练习来完成。 在听音的过程中，考生要注意掌握试题的节奏，通过听一些表示前后衔接的提示词来把握原文的脉络，这些提示词包括：and,also,too,notonly…butalso…(并列关系)； then,inaddition,moreover,furthermore(递进关系)；however,but,while,whereas(转折关系)。另外在听题的过程中，要注意对听到的词和题干中的字做同义联想，不要期望看到的和听到的字是一样的。在完成试题后，一定要检查单词的拼写、时态和单复数。

the-way-的用法讲解学习

t h e-w a y-的用法

The way 的用法 "the way+从句"结构在英语教科书中出现的频率较高, the way 是先行词, 其后是定语从句.它有三种表达形式:1) the way+that 2)the way+ in which 3)the way + 从句(省略了that或in which),在通常情况下, 用in which 引导的定语从句最为正式,用that的次之,而省略了关系代词that 或 in which 的, 反而显得更自然,最为常用.如下面三句话所示,其意义相同. I like the way in which he talks. I like the way that he talks. I like the way he talks. 一.在当代美国英语中,the way用作为副词的对格,"the way+从句"实际上相当于一个状语从句来修饰全句. the way=as 1)I'm talking to you just the way I'd talk to a boy of my own. 我和你说话就象和自己孩子说话一样. 2)He did not do it the way his friend did. 他没有象他朋友那样去做此事. 3)Most fruits are naturally sweet and we can eat them just the way they are ----all we have to do is clean or peel them . 大部分水果天然甜润,可以直接食用,我们只需要把他们清洗一下或去皮.