2 The Irregularity Strength of a Graph We now formally define such vertex-distinguishing edge colorings.Let N denote the set of positive integers and let E denote the set of edges incident with a vertex v in a graph G.An unrestricted edge coloring c:E(G)N induces a vertex coloring c:V(G→.defined by c(v)=c(e)for each vertex v of G. (2.1) EE. ected graph and(G)Nbe vertex coloring defined Proof.Let E(G)=e1,e2.....em).Since c'w)=2∑c(e) rev(G is even,there exists an even number of vertices of odd color. While no connected graph G of order 3 or more.To see this,let E(G)=fe1.e2.....em where then m>2 and let c be the edge coloring of G defined by c(ei)=2-1 for 1<i<m.Since no two vertices are incident with the same set of edges,c induces a rainbow vertex coloring.This edge coloring shows that there is always a vertex- onnected aph of size m2 where the largest color exist g edge coloringso of a graph of size m who ose large bly le than 2 For a connected graph G of size m2.the minimum of the largest colors used among the vertex-distinguishing edge colorings of G is called the irregularity strength of G and is denoted by s(G).(The strength of a multigraph M is the maximum number of parallel edges joining two vertices of M.)Therefore,for a connected graph G of order at least 3,there exists an edge coloring c:E(G) k1=1.2. .k)for every integer k with k =s(G)such that the induced (sum- defined) distingu shing but there is no ach edge coloring c:E(G) →因wi for any m with I 1≤k<s(G). Since ne rregular,it follows th very connected graph of order at least 3 must have irregularity strength at least 2.It is well known that there is exactly one connected graph Gn of order n for each n>2 containing exactly two vertices having the same degree.All of these graphs have irregularity strength 2. Proposition 2.2.If Gn is the unique connected graph of order n 3 containing exactly two vertices of equal degree,then s(G)=2. Proof.As mentioned above,s(G)>2 for every integer n2.Each such graph G n be de s h aving vertex set V(Gn)=1.v2.....vE(G if and only if i+jsn+1.Consequently. 6 2 The Irregularity Strength of a Graph We now formally define such vertex-distinguishing edge colorings. Let N denote the set of positive integers and let Ev denote the set of edges incident with a vertex v in a graph G. An unrestricted edge coloring c W E.G/ ! N induces a vertex coloring c0 W V.G/ ! N, defined by c0 .v/ D X e2Ev c.e/ for each vertex v of G: (2.1) Proposition 2.1. Let G be a nontrivial connected graph and let c W E.G/ ! N be an edge coloring of G, where c0 W V.G/ ! N is the induced vertex coloring defined in (2.1). Then there exists an even number of vertices of odd color. Proof. Let E.G/ D fe1; e2;:::; emg. Since X v2V.G/ c0 .v/ D 2 Xm iD1 c.ei/ is even, there exists an even number of vertices of odd color. While no edge coloring of the graph K2 can induce a rainbow vertex coloring defined in this manner, there is a vertex-distinguishing edge coloring for every connected graph G of order 3 or more. To see this, let E.G/ D fe1; e2;:::; emg where then m 2 and let c be the edge coloring of G defined by c.ei/ D 2i1 for 1 i m. Since no two vertices are incident with the same set of edges, c induces a rainbow vertex coloring. This edge coloring shows that there is always a vertex￾distinguishing edge coloring of a connected graph of size m 2 where the largest color used is 2m1. In general, there exist vertex-distinguishing edge colorings of a graph of size m whose largest color is considerably less than 2m1. For a connected graph G of size m 2, the minimum of the largest colors used among the vertex-distinguishing edge colorings of G is called the irregularity strength of G and is denoted by s.G/. (The strength of a multigraph M is the maximum number of parallel edges joining two vertices of M.) Therefore, for a connected graph G of order at least 3, there exists an edge coloring c W E.G/ ! Œk D f1; 2; : : : ; kg for every integer k with k s.G/ such that the induced (sum￾defined) vertex coloring c0 is vertex-distinguishing but there is no such edge coloring c W E.G/ ! Œk with this property for any integer k with 1 k < s.G/. Since no nontrivial graph is irregular, it follows that every connected graph of order at least 3 must have irregularity strength at least 2. It is well known that there is exactly one connected graph Gn of order n for each n 2 containing exactly two vertices having the same degree. All of these graphs have irregularity strength 2. Proposition 2.2. If Gn is the unique connected graph of order n 3 containing exactly two vertices of equal degree, then s.Gn/ D 2. Proof. As mentioned above, s.Gn/ 2 for every integer n 2. Each such graph Gn can be described as having vertex set V.Gn/ D fv1; v2;:::;vng where vivj 2 E.Gn/ if and only if i C j n C 1. Consequently,