2.Proper k-Binomial-Colorable Graphs 9 Theorem2.l.2.If G is a connected graph of order n≥3，thenx(G≤n+l. This topic has also been discussed in many research papers(see[1,6.12,13.15. 32,46.47,76].for example). 2.2 Proper k-Binomial-Colorable Graphs ≤2 since there are 2*subse thermore.f)ad G has order 2,then Gmust exactly (vertices of degree r for every integer r with 0<r<k.For example,the graph G of order 16=24 in Fig.2.2 has (vertices of degree r for every integerr with 0<r<4.The ner 4-edge color t():vEV(G) g of Gin Fig.2.2 has the property that For an integerk≥2，a oma graph sontaining(vertic of degree r for each integer r with 0r<k.(There is no 1-binomial graph.)Thus such a graph G has order and size -2食- A graph G is a binomial graph if G is a k-binomial graph for some integerk2 These concepts were introduced and studied in [27]. ⊙2 ④ 、3 3© 1 @,⊙ G 1234 ④人4 2 234 3③ 3④ 4 Fig.2.2 A graph of order 16 with strong chromatic index 4 2.2 Proper k-Binomial-Colorable Graphs 9 Theorem 2.1.2. If G is a connected graph of order n  3, then 0 s.G/  n C 1. This topic has also been discussed in many research papers (see [1, 6, 12, 13, 15, 32, 46, 47, 76], for example). 2.2 Proper k-Binomial-Colorable Graphs If G is a graph of order n with strong chromatic index k, then n  2k since there are 2k subsets of Œk. Furthermore, if 0 s.G/ D k and G has order 2k, then G must contain exactly k r  vertices of degree r for every integer r with 0  r  k. For example, the graph G of order 16 D 24 in Fig. 2.2 has 4 r  vertices of degree r for every integer r with 0  r  4. The proper 4-edge coloring of G in Fig. 2.2 has the property that fc0 .v/ W v 2 V.G/g D P.Œ4/ and so 0 s.G/ D 4. For an integer k  2, a k-binomial graph is a graph containing k r  vertices of degree r for each integer r with 0  r  k. (There is no 1-binomial graph.) Thus, such a graph G has order n D X k rD0 k r ! D 2k and size m D 1 2 X k rD0 r k r ! D k2k2 : A graph G is a binomial graph if G is a k-binomial graph for some integer k  2. These concepts were introduced and studied in [27]. ... ... ... .... .... .............................. ..... ..... .............................................................. ... ... ... .. .. .. .... .................. .. .. .. ... ... ... ... ...................................................... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ... . ...................................................... ... ... ... .. .... ......... ............. ..... .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ... ..... ...................................................... ... ... .. ..... ..................... .. .. ... ... ... ....................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ... ... ... ... .. .. .... .................. .. .. .. ... ... ......................................................... ......................... .......................... .......................... .. .. .. .. .. .. .. .. .. .. .. .. .. ........................... ......................... ........................... ........................... ................................................. ................................................. ................................................... .................................................. 1234 1 2 3 4 1 4 1 3 2 2 1 3 4 4 3 23 34 234 123 134 124 12 2 2 3 13 24 1 4 14 G : 0/ Fig. 2.2 A graph of order 16 with strong chromatic index 4