10 2 The Irregularity Strength of a Graph Proof.Since it is easy to see that s(C)=3 and K2)=C.we may assume tha r>3.Let G=K).Since G is a (2r-2)-regular graph of order 2r.it follows by Corollary 2.6 that s(G)>3.We show that s(G)<3 by describing a vertex- distinguishing edge coloring c:E(G)(1.2.3). Denote the partite sets of G by Vi.V2.....Vr,where Vi=fxi.yi for I <i r. We now relabel the vertices of G by u.u. u where n=2r.such that ui=x for 1 i<rand u =y for<r.Let H be the spanning subgraph of G where u,yeE(lifl≤i<j≤n and i+j≤n.Thus 2r-1-iif1≤i≤r dcgH= (2.4) 2r-iifr+1≤i≤nm. Thus deg u≥degH2≥·≥degH un and deg ui=deg ur+only when i=r.Next,we define an edge coloring E(G)(1.2.3)of G by assigning the color I to each edge of H and the color 3 to the remaining edges of G.The induced vertex coloring c is then defined by (ui)degu ui +3(2r-2-degu ui)=6r-6-2degn ui forl≤i≤n.Hence(u)≤t(2)≤…≤c(n)with equality only for(,) and c(ur+1).In particular,cu,)=c(u+1)=4r-4. We now revise the edge coloring c by replacing the color 1 of uur by 2. producing a new edge coloring c of G.The induced vertex coloring c'then satisfies the following (2r-1 if i=1 '(ui)= 6r-6-2 degu if2≤i≤r-1orr+1≤i≤n 4r-3 if i=r. This is illustrated for K4 in the following table. 1,42,8294y4为2y1 65433210 68101212141618 c() 78101312141618 Since c is a vertex-distinguishing edge coloring,it follows that s(G)<3 and so s(G)=3. e Even though each complete multipartite graph in which every partite set consists of exactly one vertex or every partite set onsists of exactly two vertices has rity strength 3.this is not the ca ase if every partite set consists of exacty thre vertices,as we now illu with the graph K33.By Corollary 2.1,s(K 3 Assume to the contrary that s(K3.3)=3.Then there is a vertex-distinguisl ng edg coloring c of G =K3.3 with induced vertex coloring c.Therefore,fc(v):v e V(G))S =(3.4.....9).Since the order of G is 6 and |S]7,every integer in 10 2 The Irregularity Strength of a Graph Proof. Since it is easy to see that s.C4/ D 3 and K2.2/ D C4, we may assume that r 3. Let G D Kr.2/. Since G is a .2r  2/-regular graph of order 2r, it follows by Corollary 2.6 that s.G/ 3. We show that s.G/ 3 by describing a vertex￾distinguishing edge coloring c W E.G/ ! f1; 2; 3g. Denote the partite sets of G by V1; V2;:::; Vr, where Vi D fxi; yig for 1 i r. We now relabel the vertices of G by u1; u2;:::; un, where n D 2r, such that ui D xi for 1 i r and unC1i D yi for 1 i r. Let H be the spanning subgraph of G where uiuj 2 E.H/ if 1 i < j n and i C j n. Thus degH ui D 8 < : 2r  1  i if 1 i r 2r  i if r C 1 i n. (2.4) Thus degH u1 degH u2  degH un and degH ui D degH uiC1 only when i D r. Next, we define an edge coloring c W E.G/ ! f1; 2; 3g of G by assigning the color 1 to each edge of H and the color 3 to the remaining edges of G. The induced vertex coloring c0 is then defined by c0 .ui/ D degH ui C 3.2r  2  degH ui/ D 6r  6  2 degH ui for 1 i n. Hence c0 .u1/ c0 .u2/  c0 .un/ with equality only for c0 .ur/ and c0 .urC1/. In particular, c0 .ur/ D c0 .urC1/ D 4r  4. We now revise the edge coloring c by replacing the color 1 of u1ur by 2, producing a new edge coloring c of G. The induced vertex coloring c0 then satisfies the following c0 .ui/ D 8 ˆˆ< ˆˆ: 2r  1 if i D 1 6r  6  2 degH ui if 2 i r  1 or r C 1 i n 4r  3 if i D r. This is illustrated for K4.2/ in the following table. u1; u2;:::; u8 x1 x2 x3 x4 y4 y3 y2 y1 degH ui 6 5 4 3 3210 c0 .ui/ 6 8 10 12 12 14 16 18 c0 .ui/ 7 8 10 13 12 14 16 18 Since c is a vertex-distinguishing edge coloring, it follows that s.G/ 3 and so s.G/ D 3. Even though each complete multipartite graph in which every partite set consists of exactly one vertex or every partite set consists of exactly two vertices has irregularity strength 3, this is not the case if every partite set consists of exactly three vertices, as we now illustrate with the graph K3;3. By Corollary 2.7, s.K3;3/ 3. Assume to the contrary that s.K3;3/ D 3. Then there is a vertex-distinguishing edge coloring c of G D K3;3 with induced vertex coloring c0 . Therefore, fc0 .v/ W v 2 V.G/g  S D f3; 4; : : : ; 9g. Since the order of G is 6 and jSj D 7, every integer in