10 2 Binomial Edge Colorings Fig.2.3 Eight k-binomial graphs for 2.3 人 G2 G6 G a 0 The unique 2-binomial graph Go and the seven 3-binomial graphs G-Gare ial hs Sinc be ue equer graphGis 3.2.2.2.1.1.1.0.its e sub oh of G not c ntaining t 1S0 ed vertex.I If H is a tree.then subdividing each edge of Ki.3 once,(2)subdividing one edge of Ki.3 twice and one edge once and (3)subdividing one edge of K1.3 three times.Thus,there are three such 3-binomial graphs.If H is not a tree,then H must be disconnected where each component contains at least two vertices.Since the maximum size of such a graph having three components is 5.it follows that has exactly two components one of order,say nd the other of order 7-.where 25.Since the size H is 6 and m size of the omponents is (-1)+(6-()=5. t be a tree and the othe a unicyclic graph (and so contain exactly one cycle).Because H has three end-vertices,H does not contain a 5 cycle.If the unicyclic component of H is a 3-cycle,then G is G4.If the unicyclic component of H is not a 3-cycle but contains a 3-cycle,then (a)this component has order 4 or 5,(b)the vertex of degree 3 lies on the 3-cycle in H and (c)the acyclic component of H is either P:or P2.If the acyclic component is P3,then G is Gs: while if the acyclic component is P2,then G is G6.If H has a 4-cycle,then G is G. nial-colo oring of a graph Gisa proper edge coloring c:E(G)→[因={1,2，，k such that the induced vertex coloring c:V(G→9().10 2 Binomial Edge Colorings Fig. 2.3 Eight k-binomial graphs for k D 2; 3 ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ....... ..... ............. ...... ............... ... ... .................... ... ... .................... ... ... ..................... ... ... ..................... ... ... ..................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... ..................... ... ... .................... ... ... ................... ... ... ..................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... .................... ... ... ................... ... ... ..................... ... ... .................... ... ... ................... ... ... .................... ... ... .................... ... ... ................... ... ... .................... ... ... .................... ... ... ....... . ............. ... ......... .. .............. ... ....... ............... ... ... ...... . ............. ... ......... .............. ... ... .................... ... ... ..................... .................. .. .. .. .. .. .. .. .. ... .............. .. .. .. .. .. .. ... ................. .. .. .. .. .. .. .. ... ................... .. .. .. .. .. .. .. .. .. ... ................. ................... .................. .. .. .. .. .. .. .. ... ............... .............. .. .. .. .. .. .. ... .. .. .. .. .. ..... ................. ................. G1 G2 G3 G4 G5 G6 : G7 : G0 The unique 2-binomial graph G0 and the seven 3-binomial graphs G1 G7 are shown in Fig. 2.3. Let’s see why G1 G7 are the only 3-binomial graphs. Since the degree sequence of a 3-binomial graph G is 3; 2; 2; 2; 1; 1; 1; 0, its size is 6. Let H be the subgraph of G not containing the isolated vertex. If H is a tree, then H must be obtained by three subdivisions of K1;3. This can be done in three ways: (1) subdividing each edge of K1;3 once, (2) subdividing one edge of K1;3 twice and one edge once and (3) subdividing one edge of K1;3 three times. Thus, there are three such 3-binomial graphs. If H is not a tree, then H must be disconnected where each component contains at least two vertices. Since the maximum size of such a graph having three components is 5, it follows that H has exactly two components, one of order `, say, and the other of order 7 `, where 2  `  5. Since the size of H is 6 and the minimum size of the two components is .` 1/ C .6 `/ D 5, one component of H must be a tree and the other a unicyclic graph (and so contains exactly one cycle). Because H has three end-vertices, H does not contain a 5- cycle. If the unicyclic component of H is a 3-cycle, then G is G4. If the unicyclic component of H is not a 3-cycle but contains a 3-cycle, then (a) this component has order 4 or 5, (b) the vertex of degree 3 lies on the 3-cycle in H and (c) the acyclic component of H is either P3 or P2. If the acyclic component is P3, then G is G5; while if the acyclic component is P2, then G is G6. If H has a 4-cycle, then G is G7. For an integer k  2, a proper k-binomial-coloring of a graph G is a proper edge coloring c W E.G/ ! Œk D f1; 2; : : : ; kg such that the induced vertex coloring c0 W V.G/ ! P.Œk/;