?

240-8501 79-2 Email: nakamoto@ynu.ac.jp

1 3 1.1...................................... 3 1.2?................................. 6 1.3..................................... 8 1.4....................................... 11 1.5 2........................................ 12 1.6......................................... 14 2 15 2.1...................................... 15 2.2..................................... 17 3 21 3.1 2................................ 21 4 24 4.1..................................... 24 4.2......................................... 26 5 29 5.1.................................... 29 5.2.................................... 30 2

1 1.1 G, V 2 E ( V 2 ) G = (V, E)., X, {x, y} E x y, G.,,. G V (G) E(G). A A., V (G) = 0 G, V (G) = 1 G. 2 G = (V, E) G = (V, E ), (V, E) (V, E ) 1., 1.1 V (G) = {a, b, c, d, e, f, g}, E(G) = {ab, ac, cb, cd, bd, dg, ge, gf} G. ( x, y V (G), V (G) 2, {x, y} V (G),, xy E(G).) a c d b e g f 1.1: G 1.1 1.2 12,. 1.2 4. (,..)., 1.3., k 6 k 1 1 (k = 0, 1, 2, 3),. 1, φ : V V, u, v V, uv E φ(u)φ(v) E. φ φ : G G, G G. 3

1.2: 1.3: 4, V 2, 2 1,.,,.,.. v v, v N G (v). G v, deg G (v).,., 0. G, deg G (v) = N G (v). G, (G) δ(g)., (G) = δ(g) = k, G,, k-. 2 2 () 2 ( 1.4 ).. X, Y 2 G G = (X, Y ). n, K n.,.,, 4

X Y 1.4: X = Y = 4 2 G = (X, Y ), ( 1.5 ).,. 1 6 2 5 3 4 1 6 2 5 3 4 1.5: K 6 C 6 1.3 2.. G 2 v 0 v 0 v 1 v i v i 1 v i+1 v i 2 v i+1 i = 1, 2,... G W = v 0 v 1 v 2 G i, j ( i j 3) v i = v j i j v i v i+1 v j, 2. G, G. G, ω(g).. 1.3 2 1. 1.4 n n 1. T n n n = 1 T 1 0 n 2 1.3 T 1 v T = T v T n 1 (n 1) 1 = n 2 T n 1 5

1.5 6.., 1.6. 1.6: 6 G 2 x, y, x y G x y, d(x, y), d G (x, y). G d(g). d(g) = max{d(x, y) : x, y V (G)} G = (V, E), V V, E E G = (V, E ) G., V = V, G.,. G, G. G, S V (G). S,, S ( S ), : V ( S ) = S E( S ) = {uv E(G) : u, v S}., V (G) V (G) G. G,, G,. F (G) G. (G, G.),,,.,.,. 1.6. 1.2?,.,,,. (?). 1.7 (), 2. 6

.,., 2. 1.8 (), ()..,.,..,.,. 1.9,., G G., G f F (G) v f., f f e, v f v f e e. G 2 ( 1.7 )., (G ) = G. 1.7: G 1.9.,, G., G G. G, G F, G.,., G. 1.10 () 3 1, 2, 3 ( 1.8 ). 1, 2, 3, 1, 2, 3.. G 1,2,3, 1,2,3.,, G H : e G f, f, e i, j, v f v f. f, 1, 2, 3, 2, (i, j, k {1, 2, 3} ), v f H 3, 2, 0 : 2 G V (G ) = F (G), G, G., E(G) = E(G ). 7

1 2 3 1.8: 1, 2, 3 i k j i j i i i i F 3, deg H (v F ) = 3., 1, 2, 3, f v f, deg H (v f ) = 0, 2. H, v F, H., 1, 2, 3. 1.3 G G.,,.,,.,. d = (d 1, d 2,..., d n ), d.,,,., : 1.11 d = (d 1, d 2,..., d n ).. d 1,..., d n, v i d i 2., d 1, d 2,..., d 2h., d = (d 1,..., d n),, { d di 1 (i = 1,..., 2h) i = (i = 2h + 1,..., n), d i., deg(v i ) = d i, h v 1 v 2, v 3 v 4,..., v 2h 1 v 2h, 1.9 d. 8

v 1 v 2 v 3 v 2h v 2h+1 v n 1.9: d,.,. 1.12 G, 2. : n. 1,,, 2.,, (, A B, B A ). 1.12. G {v 1,..., v n },.,., n 1 deg(v 1 ) > deg(v 2 ) > > deg(v n ) 0 (deg(v 1 ), deg(v 2 ),..., deg(v n 1 ), deg(v n )) = (n 1, n 2,..., 1, 0). deg(v 1 ) = n 1 deg(v n ) = 0,., 2. 1.12, n.,, 1,,.,,,. 1.13 3 6.,.,. 1.13. 1.14 6, a, a, b, b, c, c. aa, bb, cc / E(G), a., a.., a 0, 1, 2, 3, 4. 4 0, 0 4 b, b. ( 1.10.) 1.10, 3 2., 0, 1, 4., 1.10. 3 1, c, c., a 2. 1.14. 9

a 4 0 b b 3 1 2 a 4 0 b b c c 3 1 2 1.10: 6 1.15 2k, a 1, b 1, a 2, b 2,..., a k, b k. i, a i b i / E(G), a 1., b 1.,.,. 1.16 d = (d 1, d 2,..., d n ),, d 1 d 2 d n,, d = (d 2 1,..., d d1 +1 1, d d1 +2,..., d n ).. d G, d 2 1,..., d d1 +1 1, d G., G d, v i d i. k G = N G (v 1 ) {v d1 +2,..., v n }. k G = 0,, v 1 v 2, v 3,..., v d1 +1, G v 1 d., k G > 0., 2 i d 1 + 1 < j n (i, j), v 1 v i, v j. deg(v i ) deg(v j ) 1, v i v j (x ). G = G {v i x, v 1 v j } {v 1 v i, v j x}, G d, k G = N G(v 1 ) {v d1 +2,..., v n } < k G., d, k G0. = 0 G 0, k G. (k G = 0, k G > 0, k G.), 2,,, 2,,. 1.16, : (4, 4, 3, 2, 1), (4, 4, 3, 3, 2), (5, 4, 3, 3, 2, 1), (2, 2, 2, 2, 1, 1). (4, 4, 3, 2, 1) (3, 2, 1, 0) (1, 0, 1). 10

(4, 4, 3, 3, 2) (3, 2, 2, 1) (1, 1, 0) (0, 0). (5, 4, 3, 3, 2, 1) (3, 2, 2, 1, 0) (1, 1, 0, 0) (0, 0, 0). (2, 2, 2, 2, 1, 1) (1, 1, 2, 1, 1) = (2, 1, 1, 1, 1) (0, 0, 1, 1) = (1, 1, 0, 0) (0, 0, 0)., 1.16,. 3,,. 1.4,. 1.1. 1.17 K n ( n) 2 = n 1 i=1 i = n(n 1) 2. (, ( n k) 2 3, n k.). (1). 2, K n ( n) 2 = 1 2n(n 1). (2). n n 1., 1.13, 1 2n(n 1). (3). K 1 0, K 2 0 + 1,, K n 1 1 + + (n 2), K n K n 1, K n (0 + 1 + + (n 2)) + n 1 = n 1 k=1 = 1 2n(n 1). 1.18 K n 3 C 3., C 4 C 5.. 3, 1 C 3, C 3 ( n 3). k n, K n C k. K n k, ( n k) (k 1)!., C k ( ) 1 n n! (k 1) = 2 k 2k(n k)!. 1.19 n 1, n 2 (n 1 n 2 ) n 1 + n 2 = 30., ( n 1 ) ( 2 + n2 ) 2, n 1 = 30, n 2 = 0., n 1 n 2 n k n 1 + + n k = n, k ( ni ) i=1 2.. () n 1 + n 2 = 30 (n 1 n 2 0), n 2 = 30 n 1 (15 n 1 30), ( ) ( ) n1 n2 + = 1 2 2 2 n 1(n 1 1) + 1 2 n 2(n 2 1) = 1 2 (n2 1 n 1 + (30 n 1 ) 2 (30 n 1 )) 3 ( n k) = n C k. = (n 1 15) 2 + 210. 11

n 1 = 30 435. (,.) () ( n 1 ) ( 2 + n2 ) 2, 1.17, Kn1 K n2. n 2 1, E(K n1 +1) + E(K n2 1) > E(K n1 ) + E(K n2 ), ( n 1 ) ( 2 + n2 ) 2, n 1 = 30, n 2 = 0. ( 30) 2 = 435., K n1 K n2 K nk, n 1 = n, n 2 = = n k = 0, ( n 2). 1.5 2, 2. 1.20 G 2, G.. 2,., 2,. G. G v 0., X, Y V (G) : X = {u V (G) : d G (v 0, u) } Y = {u V (G) : d G (v 0, u) }. G, X Y = V (G),,, X Y =. G 2, x, x X, xx E(G) (, y, y V (G), yy E(G))., P = v 0 P x, xx, x P v 0 (, P v 0 x, P v 0 x.) P, P. 1.9 1.20,. 1.21 2.. G 2., 1.20, G C., 1.9, C..,. 1.22 5, 3,,.. G., G, G G., 1.21, G 2, G = (X, Y ) (X, Y G )., G 5 v 1, 3., v X., Y 3, Y X 3., X v, X Y 3.. 12

,. n, Q n n ( 1.11 ): V (Q n ) = {(a 1, a 2,..., a n ) : a i {0, 1}} E(Q n ) = {xy : d h (x, y) = 1, x, y V (Q n )},, x = (a 1,..., a n ) y = (b 1,..., b n ), x, y d h (x, y) d h (x, y) = {i : a i b i }. 0 1 10 11 00 01 110 111 010 011 100 101 000 001 1.11: n 1.23 Q n,. (i) V (Q n ) = 2 n, (ii) E(Q n ) = n2 n 1, (iii) d(q n ) = n, (iv) Q n 2.. (i) (a 1, a 2,..., a n ), a i 0 1. (ii) n. (i), Q n 2 n,, E(Q n ) = n 2 n /2 = n2 n 1. (iii) (0, 0,..., 0) (1, 1,..., 1) n, 2 n. (iv) (a 1,..., a n ), n i=1 a i.,., Q n 2. 1.24 4 Q 4., Q 4 4 0, 1. 13

1.6 G, G G, V (G) = V (G) E(G) = {uv : uv / E(G)}., G = G., G = G ( 1.12 ). 1. G G 1.12: C 5 1.25 G, G G.. G, G. G H 1,..., H k, G k K V (H1 ),..., V (H)., G. 1.26.. G, G 1.25.. 1.27 n 2, n 0, 1 (mod 4).. G, E(G) = E(G)., 1.17, E(G) + E(G) = E(K n ) = 1 2 n(n 1)., E(G) = 1 4n(n 1),, n 0, 1 (mod 4). G G 1.13:. 4 P 4 = v 1 v 2 v 3 v 4., 1.12 C 5 5., n H, n + 4. P 4 v 2, v 3 H K, K ( 1.13 ). 14

2 G G 1., G, G 1., 2. 2.1,,,,, 2,.,,,. G, 1. 2.1: (, ). 2.1 G, G,, G.,,. 2.1. 2.2 G, G,, G 0 2. 2.1.,,. (,.) 2.1.. G,, G., G, v, v v., v. 15

. G. G,, 2, G,,., G 4. G v 0, 2 W., W v 0., v, W v, v., G = G E(W ), G H 1,..., H k. H i.,, W, H i.,, H i W i., G, W 1,..., W k, G W W i. G, W W i v i. W v 1,..., v k., v 0, W., v 1, W 1, W 1 v 1, W., W v 2, W 2., v i W i, W W 1 W k G. 2.1 2.2. 2.2., G,, 0 2., G,, 2.1, G,., G 2 u, v, G = G uv, 2.1, G W. G W uv u, v G., 2.1. 2.1,., (, ). 2.3 G,., G. 2.. G G,., 1.21, G 2., G,, 2 (). B 1,..., B k G. B i B i., e E(G) 1 B i 1. B : V (B) = B i (i = 1,..., k) E(B) = {B i B j : B i B j }. G, B., B T B. B i B j E(B) B i, B j, 1 v ij B i B j., k i=1 B i W., T B B 1 1 B i (i = 2,..., k)., W 1 = B 1., W i 1, W i 1 B i v li V (G) (, B l B i E(T B ) ). W i 1 B i. W i. 16

,, G W = W k.. G. G. G 2,., G 4 v. v v e 1,..., e l (, e i = vv i ). v G, G {e 1, e 2 }. (, G {e 1, e 2 }, G {e 2, e 3 }, e 1, e 2.), G = (G {e 1, e 2 }) v 1 v 2, G. G G,,,,, W. W = (W v 1 v 2 ) {e 1, e 2 } G.,, 2.1. 2.2,.,.,,.,.,. 2.4 2.2. (i) (ii) (iii) 2.2: 2.4 YES NO., YES 1, NO, 1. 2.4 (i). (i)., (i).. ( 11.) (ii).,. 17

, 2,., 2. ( 1.21.),,,.,. 2.5 2 G = (X, Y ), X = Y. 2.4 (ii). (ii) 2., 2.5,,. (iii), (ii). (iii),. (, 2.) t. G, G S S V (G), t S ω(g S), G t-., s t, G s- t-. t(g) = max{t : G t- } = min S S ω(g S) S G. G, S =, ω(g S) = 0, t(g) = 0., K m ω(k m S) > 1 S V (K m ), t(k m ) =., G,.,,,,.,. 2.6 G, G 1-.. G 1-., S V (G), G S G S S,, ω(g S) > S. G S H 1,..., H k (k > S ), H i H j S, H 1,..., H k, S., G. 2.4(iii). 2.2(iii) 5 3, 4., 1-, 2.6, (iii). P ( 2.3 ) 1-. (P 4 3.), 2.7, P., 2.7, 1-. 18

2.3: 2.7.. P 5 S = {s 1, s 2, s 3, s 4, s 5 }, T = {t 1, t 2, t 3, t 4, t 5 } (, i s i t i E(P )). P C, S T 5,, 2 4,., s 1 t 1 E(C), s 2 t 2 / E(C)., C (3-, v 3 e 1, e 2, e 3 1, e 1, C, e 2, e 3 C )..,,. 2.8 () n 3 G, 2 u, v V (G),, G. deg(u) + deg(v) n.. G. G, 2 u, v V (G), G {uv}, G u v x 1 x 2 x n ( u = x 1, v = u n )., S = {x i : x i 1 N(v)}, N(u) S V (G) {u}., deg(u) + deg(v) = N(u) + S n, N(u) S. x k N(u) S, x 1 x k x k+1 x n x k 1 x k 2 x 2 G. G. 2, : 2 K m,m+1., 2.5,. K m,m+1 2, 2 2m., K m,m+1 2 u, v, deg(u) + deg(v) 2m = V (K m,m+1 ) 1 19

,. 2.8. 2.9 () n 3 G, δ(g) n 2., G. G v, deg(v) n 2, G 2 u, v, deg(u) + deg(v) n 2 + n 2 = n., 2.8, G., K m,m+1, n 1., 2.9. 20

3 3.1 2 3.1 17 R (1 ). 17,. 3.1, 2 34 G R. R, G R 17. G R 2,,,., G R, G R, R. 3.1: R G R G e, e, e e. M E(G). uv M, u, v M,, M. M, M. M (, M ), M., M.,., G, G.,,. 3.1 2 G = (X, Y ), X = Y., 3.1. 3.2 3.2 G. 3.2. (i), (ii), k k 1.,. 21

(i) (ii) 3.2: (iii) (iii), 1.21, 2. 3.1. 3.2 (i), (ii),,., 2,. 3.3 G = (X, Y ) 2, X, Y V (G). G X, S X, S N G (S)., N G (S) = s S N G(s).,. G, M E(G). G P = e 1 e 2 e n ( e i E(G)), M, P M. P = e 1 e n M, M = (M E(P )) (E(P ) M) G, M > M.. 3.3. X, S X, N G (S) {y Y : s S, sy M} = S.,., G M u X., S = {x X : u x M }., u, u 0, u S., S = {u, s 1,..., s k }., s i M, s i y i Y., s S M y Y {y 1,..., y k }, sy E(G) M, u y M, u y M, M., M., sy., N G (S) = {y 1,..., y k },,. k + 1 = S > N G (S) = k 22

3.4 () G = (X, Y ) X = Y 2. G, S X,.. 3.3, X = Y. S N G (S).,. 3.3. Y. k, A i Y (i = 1,..., k)., 1 {A 1,..., A k }, a i A i k {a 1,..., a k }. {a 1,..., a k } {A 1,..., A k }.. X = {A 1,, A k }., a Y A i X, a A i, X Y 2 B(X, Y ) = G., X, G, X.,. 3.5 {A 1,..., A k }, A 1,..., A k l l.. 3.3 1, (, )., X (, f : X {0, 1, 2,...} ),. 3.6 G = (X, Y ) 2, f : X {0, 1, 2,...}., G H, (i) V (H) X, (ii) x X, deg H (x) = f(x), (iii) y Y, y V (H), deg H (y) = 1,, S X,. f(x) N G (S) x S x X, f(x) = 1 f, x S f(x) = x S 1 = S, 3.6 3.3. 3.3. 1,. 23

4 4.1 (, ).,,,,,,. (,,.) 4.1 () G, : V (G) E(G) + F (G) = 2.. n. G, G, G, 1.4, n 1. 1, n (n 1) + 1 = 2,. E(G) n, G T, e E(G) E(T ). G = G {e}, G,, n (E(G ) + F (G ) = 2., G e G., e, G, e, G., G e, F (G) = F (G ) + 1., n E(G) + F (G) = n ( E(G ) + 1) + ( F (G ) + 1) = 2,. 4.2 G, : G. E(G) 3 V (G) 6.. G 3, 3 F (G) 2 E(G) ( G )., F (G),. 4.3 5 4. 24

. 1.6, G, G G. V i G i, 3,, i=3,4,5,... V i = V ( G) ; i=3,4,5,... iv i = 2 E( G)., 4.1, V ( G) E( G) + F ( G) = 2. G, 2 E( G) = 3 F ( G), 2 E( G) = 6 V ( G) 12 1.,, i=3,4,5... iv i = 6 i=3,4,5,... V i 12. (6 i)v i = 12. i=3,4,5... 3V 3 + 2V 4 + V 5 = 12 + (i 6)V i 12 i=7,8,... 3(V 3 + V 4 + V 5 ) 3V 3 + 2V 4 + V 5 12, V 3 + V 4 + V 5 4. v V (G), deg G(v) deg G (v), G 5 4. 4.4 G, E(G) 2 V (G) 4, 3.. G, 2 E(G) 4 F (G)., F (G),., G d d = 2 E(G) V (G) = 4 8 V (G) < 4., G 3. 4.5 K 5 K 3,3.. K 5 5 10., 4.2. K 3,3 6 9. K 3,3,, 4.4. 1 5,, : 4.2, G d d = v V (G), 5. deg G (v) = 2 E(G) 6 V (G) 12. v V (G) deg G(v) V (G) = 2 E(G) V (G) 6 12 V (G) < 6 25

4.2,,..,,., G, G 2-, 2-,,., 2-, {(x, y) : x 2 + y 2 < 1} 2.. G, G, G. 4.6 4.1 5.., G p q-. G 2 2, P, p, q 3. G, : V (G) E(G) + F (G) = 2. q V (G) = p F (G) = 2 E(G), 1 p + 1 q 1 2 = 1 E(G) ( ). ( ) p q, p q. q 4, ( ), q = 3., 1 p 1 6 = 1 E(G), p p = 3, 4, 5., E(G) = 6, 12, 30.,. ( 4.1, 4.1.) 4.1: p q E(G) 3 3 6 3 4 12 4 3 12 3 5 30 5 3 30,. 4.7 G T (G) G T (G). (, T (G) = T (G).) 2 X Y,, φ : X Y. φ. 26

4.1:. G T, G T : E(T ) = {e : e / E(T )}., e E(T ) e E(G ), ( 1.9)., T,. T, T 1., G 2 F, F F (G), T, G., T. T C, T C F F. F F C, G. T., T G., G G, (T ) = T.,.,. (,.),.,. (?) T l(t )., T, 2 l(t ) 4. 4.8 4.2, 11. 4.2 T, l(t ) = 4 6, l(t ) = 3 3, l(t ) = 2 1., T,,, 1 ( 4.3 )., 3,., 1, 1.,, : 3 H T, T H, T T σ : T T, H. 27

(1) (2) (3) (4) (5) (6) (7) (8) (9) (10) (11) 4.2: 4.3: 4.9., 4.7,,., T, T, 4.7 T, T, : 4.10,. 4.11.,.. Q,,, Q G., 4.7,. 28

5 5.1 G k-, G 2 k G. G k-, G k-. G χ(g), G. 5.1. (., χ(g) = k, G k-,, (k 1)-.) 5.2 m G, : (G,.) χ(g) 1 + 1 + 8m. 2. G k, V (G) = V 1 V 2 V k V (G)., V i i (i = 1,..., k). i, j, v i V i v j V j, v i v j E(G)., V i V j, χ(g) = k., m ( ) k k(k 1) = 2 2, k,. 5.3 G, χ(g) (G) + 1..... 1, 0,., (G) k, χ(g) k + 1. G v, G = G v. (G ) (G) k,, χ(g ) k + 1., N G (v) k, N G (v) k, v 1., χ(g) k + 1.,. 5.1.,..,,. 29

e f d d a c f ab c b e 5.1:,,, G. ( 5.1.),., G G, G,., χ(g) 1,. 5.2,. 1. 5.4 (), 4. G, 4.,, 2 2,. 5.5 (, ) 4-. 4, 6,. 5.6 6-... 6,. 4.3, G 5 v., G {v} 6-. G v 5, 6, v. 5.6,, 1. 5.7 5-. 1 1852,., 1878,. 1,, 18.,,. 1977,,.,, 1482,.,,,. 30

.. G, 4.3, 5 v., G = G {v} 5-. v 4, 5.6 G 5-., deg G (v) = 5,, v v 1, v 2, v 3, v 4, v 5 G,., G v i i (i = 1, 2, 3, 4, 5)., G 5-, v 1 3, v 1, G 5-., v 1 3, v 1 3., v 1 3., 3 1, v 1 1, v 1 3, v 1.,, v, v 1, 3 1 v 3, v. (1, 3)-., v 2 4., v 2, G 5-. v 2 4, (2, 4)-, v 2 v 4 (1, 3)-, (2, 4)-., v 2 4, G 5-. G, G,.. G G. 5.8 3-..,,, G (), 3-, 3-., G, e, e 2 : n. n = 3,. n 4, G f., G f 2 H K., H K f 2 v H v K. G, v H v K, G e, e 2. G n 3. n = 3, 3-. n 4, G 2 v, G = G {v}. G,, G 3-. v 2, G 3-. 5.8,. 5.9 () n.,. ()n,,.., n,. n n., n. 31

. n, n G. 5.8, G 3-., n 3.. G,,, n 3. 12, 4. 1 2., 12, 4., n 0(mod 3)., n 3 n, n 3. 32