Introduction to Graph Theory West 2e solutions 图论导引 第二版 West 答案

所需积分/C币:50 2014-12-22 00:03:46 3.35MB PDF

好东西不多说了 图论导引 英文版 第二版 West 答案
Solutions Preface Comments just to state the result and give an example (the next edition will include There are several underlying themes in the course, and mentioning a purely inductive proof that uses only determinant expansion, not the these at appropriate moments helps establish continuity. These include Cauchy-Binet Formula). Students find the material on graceful labelings 1) TONCAS (The Obvious Necessary Condition(s) are Also Sufficient) enjoyable and illuminating; it doesnt take long, but also it isnt required 2)Weak duality in dual maximation and minimization problems The material on branchings should certaily be skipped in this course 3)Proof techniques such as the use of extremality, the paradigm for induc- 2.3: Many students have seen rooted trees in computer science and tive proofs of conditional statements, and the technique of transforming a find ordinary trees unnatural; Kruskal's algorithm should clarify the dis- problem into a previously solved problem tinction. Many CS courses now cover the algorithms of Kruskal, Dijkstra, Students sometimes find it strange that so many exercises concern and Huffman; here cover Kruskal and perhaps Dijkstra(many students the Petersen graph. This is not so much because of the importance of the have seen the algorithm but not a proof of correctness), and skip huffman Petersen graph itself, but rather because it is a small graph and yet has complex enough structure to permit many interesting exercises to be asked. Chapter 3 3.1: Skip "Dominating Sets, but present the rest of the section Chapter 1. In recent yo ears,most students enter the course having 3.2: Students find the hungarian algorithm difficult; explicit examples been exposed to proof techniques, so reviewing these in the first five sec- need to be worked along with the theoretical discussion of the equality tions has become less necessary; remarks in class can emphasis techniques subgraph. " Stable Matchings"is very popular with students and should be as reminders. To minimize confusion, digraphs should not be mentioned presented unless far behind in schedule. Skip"Faster Bipartite Matching until section 1.4; students absorb the additional model more easily after 3. 3: Present all of the subsection on tutte s 1-factor theorem The becoming comfortable with the first material on f-factors is intellectually beautiful and leads to one proof of 1.1: p3-6 contain motivational examples as an overview of the course the Erdos-Gallai conditions, but it is not used again in the course and is an this discussion should not extend past the first day no matter where it aside". Skip everything on Edmonds'Blossom algorithm: matching algo ends (the dcfinitions are later repeated where needed). The material on rithms in general graphs are important algorithmically but would require the Petersen graph establishes its basic properties for use in later examples too much time in this course this is"recommended reading and exercises 1.2: The definitions of path and cycle are intended to be intuitive; one shouldnt dwell on the heaviness of the notation for walks Chapter 4 1.3: Although characterization of graphic sequences is a classical topic 4.1: Students have trouble distinguishingk-connected from"connec some reviewers have questioned its importance. Nevertheless, here is a tivity k”and" bonds”from“ edge cuts”. Bonds are dual to cycles in the computation that students enjoy and can perform matroidal sense; there are hints of this in exercises and in Chapter 7, but 1.4: The examples are presented to motivate the model; these can be the full duality cannot be explored before Chapter 8 skipped to save time. The de Bruijn graph is a classical application. It is 4.2: Students find this section a bit difficult. The proof of 4.2.10 is desirable to present it, but it takes a while to explain similar to that of 4.2.7, making it omittable, but the application in 4.2.14 is appealing. The details of 4.2.20-21 can be skipped or treated lightly, Chapter 2 since the main issue is the local version of Menger,s theorem. 4.2.24-25 are 2.1: Characterization of trees is a good place to ask for input from the appealing applications that can be added; 4.2.5 (CSDR) is a fundamental class, both in listing properties and in proving equivalence. result but takes a fair amount of effort 2.2: The inductive proof for the prufer correspondence seems to be 4.3: The material on network flow is quite easy but can take a long easier for most students to grasp than the full bijective proof; it also illus- time to present due to the overhead of defining new concepts. The basic trates the usual type of induction with trees. Most students in the class idea of 4.3. 13-15 should be presented without belaboring the details too have seen determinants, but most have considerable difficulty understand much. 4.3.16 is a more appealing application that perhaps makes the point ing the proof of the Matrix Tree Theorem; given the time involved, it is best more effectively. Skip "Supplies and Demands Solutions Preface Chapter 5 Characterization of Line graphs", although if time and interest is plenti 5.1: If time is short, the proof of 5. 1.22(Brooks'Theorem)can be merely ful the necessity of Krausz's condition can be explained sketched 7.2: Chvatal's theorem(7.2. 13)is not as hard to present as it looks if 5.2: Be sure to cover Furans Theorem, Presentation of dirac's the the instructor has the statement and proof clearly in mind. Nevertheless orem in 5. 2.20 is valuable as an application of the Fan Lemma (menger's the proof is somewhat technical and can be skipped(the same can be said Theorem). The subsequent material has limited appeal to undergraduates. of 7 2.17). More appealing is the Chvatal-Erdos Theorem(7.2. 19), which 5.3: The inclusion-exclusion formula for the chromatic polynomial is rtainly should be presented Skip"Cycles in Directed graphs derived here(5.3.10)without using inclusion-exclusion, making it access 7.3: The theorems of Tait and grinberg make a nice culmination to ble to this class without prerequisite. However, this proof is difficult for the required material of the course. Skip "Snarks"and "Flows and Cycle students to follow in favor of the simple inclusion-exclusion proof, which Covers". Nevertheless, these are lively topics that can be recommended for will be optional since that formula is not prerequisite for the course. Hence advanced students this formula should be omitted unless students know inclusion-exclusion Chordal graphs and perfect graphs are more important, but these can also Chapter 8. If time permits, material from the first part of sections of be treated lightly if short of time. Skip "Counting Acyclic Orientations Chapter 8 can be presented to give the students a glimpse of other topics The best choices for conveying some understanding in a brief treatment are Chapter 6. Section 8.3 (Ramsey Theory or Sperner's Lemma) and Section 8.5 Random 6.1: The technical definitions of objects in the plane should be treated Graphs). Also possible are the Gossip Problem(or other items) from Sec- very lightly. It is better to be informal here, without writing out formal tion 8.4 and some of the optional material from earlier chapters. The first definitions unless explicitly requested by students. Outerplanar graphs part of Section 8. 1(Perfect Graphs)may also be usable for this purpose if are useful as a much easier class on which to solve problems(exercises!) perfect graphs have been discussed in Section 5.3. Sections 8.2 and 86re like those on planar graphs; 6. 18-20 are fundamental observations about quire more investment in preliminary material and thus are less suitable outerplanar graphs, but other items are more important if time is short. for giving a“ glimpse” 6.1.28(polyhedra) is an appealing application but can be skipped 6.2 The preparatory material 6. 4-7 on Kuratowski's Theorem can be presented lightly, leaving the annoying details as reading; the subsequent material on convex embedding of 3-connected graphs is much more inter- esting Presentation of the planarity algorithm is appealing but optional skip the proof that it works. 6.3 The four color problem is popular; for undergraduates, show the flaw in Kempe's proof (p271), but dont present the discharging rule un- less ahead of schedule. Students find the concept of crossing number easy to grasp but the results are fairly difficult; try to go as far as the recur sive quartic lower bound for the complete graph. The edge bound and its geometric application are impressive but take too much time for under- graduates. The idea of embeddings on surfaces can be conveyed through the examples in 6.3.21 on the torus. Interested students can be advised to read the rest of this section Chapter 7. 7.1: The proof of Vizing 's Theorem is one of the more difficult in the course, but undergraduates can gain follow it when it is presented with sufficient colored chalk. The proof can be skipped if short of time. Skip Chapter 1: Fundamental Concepts Section 1. 1: What Is a graph? 1. 1.5. Ifevery vertex of a graph g has degree 2, then g is a cycle--FALSE Such a graph can be a disconnected graph with each component a cycle (lf infinite graphs are allowed, then the graph can be an infinite path 1.FUNDAMENTAL CONCEPTS 1.1.6. The graph below decomposes into copies of pg 1.1. WHAT IS A GRAPH? 1.1.1. Complete bipartite graphs and complete graphs. The complete bipar 1.1,7. a graph with more than six vertices of odd degree cannot be decom tite graph Km.n is a complete graph ifand only ifm n= l or m, n)=(1, 0) posed into three paths. Every vertex of odd degree must be the endpoint of some path in a decomposition into paths. Three paths have only six 1.1. 2. Adjacency matrices and incidence matrices for a 3-vertex path endpoints. 01 010 00 100 10 1. 8. Decompositions ofa graph. The graph below decomposes into copies 010 of K1.3 with centers at the marked vertices. It decomposes into bold and solid copies of P4 as shown 1 10 10 0 10 0 10 11 Adjacency matrices for a path and a cycle with six vertices 010000 01000 101000 101000 010100 010100 001010 001010 000101 1. 1. 9. A graph and its complement. With vertices labeled as shown, two 000101 000010 100010 vertices are adjacent in the graph on the right if and only if they are not adjacent in the graph on the left. 1.1.3. Adjacency matrix for Km 01 10 h 1. 1.4.G= H if and only if g= H. If f is an isomorphism from g to H, then f is a vertex bijection preserving adjacency and nonadjacency, and 1.1.10. The complement of a simple disconnected graph must be connected hence f preserves non-adjacency and adjacency in g and is an isomor TRUE. A disconnected graph G has vertices x, y that do not belong to a phism from g to H. The same argument applies for the converse, since the path. Hencex and y are adjacent in G. furthermore x and y have no com- complement of G is G mon neighbor in G, since that would yield a path connecting them. Hence 3 Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? every vertex not in (x, y) is adjacent in g to at least one of [x, y]. Hence color. Each pair of adjacent squares has one of each color, so the remaining every vertex can reach every other vertex in G using paths through Ir, yl squares cannot be partitioned into sets of this type 1.1.11. Maximum clique and ma. mum independent set. Since two ver Generalization: the two partite sets of a bipartite graph cannot be tices have degree 3 and there are only four other vertices, there is no clique matched up using pairwise-disjoint edges if the two partite sets have un of size 5. A complete subgraph with four vertices is shown in bold equal sizes Since two vertices are adjacent to all others, an independent set con 1.1. 15. Common graphs in four families: A= paths, B=cycles, C which the maximum size of an independent set is two, as marker p,in taining either of them has only one vertex. Deleting them leaves Pa, in [complete graphs), d= bipartite graphs AnB= 0: In a cycle, the numbers of vertices and edges are equal but this is false for a path AnC=KI. K2): To be a path, a graph must contain no cycle AnD=A: non-bipartite graphs have odd cycles B∩C=Ka: Only when n=3 B∩D={C2k:k≥2}: odd cycles are not bipartite. CnD=[K1, K2]: bipartite graphs cannot have triangles 1.1.12. The Petersen graph. The Petersen graph contains odd cycles, so it is not bipartite; for example, the vertices 12, 34, 51, 23, 45 form a 5-cycle 1.1. 16. The graphs below are not isomorphic. The graph on the left has four The vertices 12, 13, 14, 15 form an independent set of size 4, since any cliques of size 4, and the graph on the right has only two. Alternatively, the two of these vertices have 1 as a common element and hence are nonadja- complement of the graph on the left is disconnected(two 4-cycles), while cent. Visually, there is an independent set of size 4 marked on the drawing the complement of the graph on the right is connected (one 8-cycle) of the Petersen graph on the cover of the book. There are many ways to show that the graph has no larger independent set Proof 1. Two consecutive vertices on a cycle cannot both appear in an independent set, so every cycle contributes at most half its vertices. Since the vertex set is covered by two disjoint 5-cycles, every independent set has size at most 4 Proof 2. Let ab be a vertex in an independent set s, where a, bE [5]. We show that s has at most three additional vertices Thc vertices not adjacent to ab are ac, bd, ae, bc, ad, be, and they form a cycle in that order. 1.1. 17. There are exactly two isomorphism classes of 4-regular simple Hence at most half of them can be added to s graphs with 7 vertices. Simple graphs G and h are isomorphic if and only if their complements G and H are isomorphic, because an isomor 1. 13. The graph with vertex set (0, 1]and x<>y when x and y differ in phism V(G)->V(H) is also an isomorphism from g to H, and vice one place is bipartite. The partite sets are determined by the parity of the versa.Hence it suffices to count the isomorphism classes of 2-regular sim- number of I's. Adjacent vertices have opposite parity. (This graph is the ple graphs with 7 vertices. Every component of a finite 2-regular graph is a k-dimensional hypercube; see Section 1. 3.) cycle. In a simple graph, each cycle has at least three vertices. Hence each 1.1.14. Cutting opposite corner squares from an eight by eight checkerboard class it determined by partitioning 7 into integers of size at least 3 to be the sizes of the cycles. The only two graphs that result are Cr and C3+C4 leaves a subboard that cannot be partitioned into rectangles consisting of a single cycle or two cycles of lengths three and four. two adjacent unit squares. 2-coloring the squares of a checkerboard so that adjacent squares have opposite colors shows that the graph having l.1. 18.Isomorphism. Using the correspondence indicated below, the first vertex for each square and an edge for each pair of adjacent squares two graphs are isomorphic; the graphs are bipartite, with u: <> U; if and is bipartite The squares at opposite corners have the same color; when only if i+j. The third graph contains odd cycles and hence is not isomor- these are deleted, there are 30 squares of that color and 32 of the other phic to the e others. Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? the two drawings, the two adjacency matrices are the same, but that is harder to verify 4 l2 G is not isomorphic to F or to H. In F and in I, the numbers form an independent set, as do the letters. Thus F and H are bipartite The graph ∥3U1 G cannot be bipartite, since it contains an odd cycle. The vertices above the horizontal axis of the picture induce a cycle of length 7 It is also true that the middle graph contains a 4-cycle and the others Visually, the first two graphs are @3 and the graph obtained by delet- do not, but it is harder to prove the absence of a 4-cycle than to prove the ing four disjoint edges from K4.4. In 23, each vertex is adjacent to the absence of an odd cycle vertices whose names have opposite parity of the number of 1s, except for the complementary vertex. Hence Q3 also has the structure of K4.4 with four disjoint edges deleted; this proves isomorphism without specifying an explicit bijection g 3 1. 1. 19. Isomorphism of graphs. The rightmost two graphs below are iso morphic. The outside 10-cycle in the rightmost graph corresponds to the intermediate ring in the second graph. Pulling one of the inner 5-cycles of the rightmost graph out to the outside transforms the graph into the same drawing as the second graph 1.1.21. Isomorphism. Both graphs are bipartite, as shown below by mark The graph on the left is bipartite, as shown by marking one partite set ing one partite set. In the graph on the right, every vertex appears in It cannot be isomorphic to the others, since they contain 5-cycles eight 4-cycles. In the graph on the left, every vertex appears in only six 4-cycles (it is enough just to check one). Thus they are not isomorphic Alternatively, for every vertex in the right graph there are five vertices having common neighbors with it, while in the left graph there are six such vertices YA 产设 1. 1. 20. Among the graphs below, the first ( F)and third (h)are isomorphic, and the middle graph( G) is not isomorphic to either of these F and h are isomorphic. We exhibit an isomorphism(a bijection from V()to V(H) that preserves the adjacency relation). To do this, we name 1. 22. Isomorphism of explicit graphs. Among the graphs below, the vertices of F, write the name of each vertex of f on the corresponding [G1, G2, Gs) are pairwise isomorphic. Also G3= G4, and these are not vertex in H, and show that the names of the edges are the same in H and isomorphic to any of the others. Thus there are exactly two isomorphism F. This proves that h is a way to redraw F. We have done this below using classes represented among these graphs the first eight letters and the first eight natural numbers as names To prove these statements, one can present explicit bijections between To prove quickly that the adjacency relation is preserved, observe that vertex sets and verify that these preserve the adjacency relation(such as 1, a, 2, b, 3, C, 4,d, 5, e, 6,f,7,8, 8, h is a cycle in both drawings, and the ad by displaying the adjacency matrix for example). One can also make other ditional edges 1c, 2d, 3e, 4 f, 5g, 6h, 7a, 8b are also the same in both draw- structural arguments. For example, one can move the highest vertex in G ings. Thus the two graphs have the same edges under this vertex corre down into the middle of the picture to obtain G; from this one can list the spondence. Equivalently, if we list the vertices in this specified order for desired bijection Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? One can also recall that two graphs are isomorphic if and only if their different lists of vertex degrees(similarly for 4 edges). For 3 edges, the complements are isomorphic. The complements of G1, G2, and Gs are c three isomorphism classes have degree lists 3111, 2220, and 2211, all dif- cles of length 7, which are pairwise isomorphic. Each of G3 and G4 consists ferent. Hence nonisomorphic simple graphs with the same vertex degrees of two components that are cycles of lengths 3 and 4; these graphs are must have at least five vertices isomorphic to each other but not to a 7-cycle 1. 1.24. Isomorphisms for the Petersen graph. Isomorphism is proved by giving an adjacency-preserving bijection between the vertex sets. For picto rial representations of graphs, this is equivalent to labeling the two graphs with the same vertex labels so that the adjacency relation is the same in both pictures; the labels correspond to a permutation of the rows and G columns of the adjacency matrices to make them identical. The various drawings of the Petersen graph below illustrate its symmetries; the label- 1.1.23. Smallest pairs of nonisomorphic graphs with the same vertex de ings indicate that these are all"the same"(unlabeled)graph The number grees. For multigraphs, loopless multigraphs, and simple graphs, the re of isomorphisms from one graph to another is the same as the number of appear below. We must prove that these constructions are smalles ounds quired numbers of vertices are 2, 4, 5; constructions for the upper be isomorphisms from the graph to itself. 24 51 34 23 45 1 52 35 34 a)general b)loopless c)simple a)With 1 vertex, every edge is a loop, and the isomorphism class 12 23 determined by the number of edges, which is determined by the vertex 41 52 degree. Hence nonisomorphic graphs with the same vertex degrees have 35 41 at least two vertices b)Every loopless graph is a graph, so the answer for loopless graphs 12 12 is at least 2. The isomorphism class of a loopless graph with two vertices 35 34 35 34 is determined by the number of copies of the edge, which is determined by the vertex degrees. The isomorphism class of a loopless graph with three vertices is determined by the edge multiplicities. Let the three vertex 41 52 41 52 degrees be a, b, C, and let the multiplicities of the opposite edges be x, y, z, 24 51 where Since a= y +z,b=x+z, and c=x+ y, we can solve for the multiplicities in terms of the degrees byx =(b+c-a)/ 2, y=(a+c-b)/2 23 13 and z =(a+b-c)/2. Hence the multiplicities are determined by the 23 13 degrees, and all loopless graphs with vertex degrees a, b, c are pairwise 4 isomorphic. Hence nonisomorphic loopless graphs with the same vertex degrees have at least four vertices 1.1.25. The Petersen graph has no cycle of length. 7. Suppose that the Pe c)Since a simple graph is a loopless graph, the answer for simple tersen graph has a cycle C of length 7. Since any two vertices of C are graphs is at least 4. There are 11 isomorphism classes of simple graphs connected by a path of length at most 3 on C, any additional edge with with four vertices. For each of 0, 1, 5, or 6 edges, there is only one isomor endpoints on C would create a cycle of length at most 4. Hence the third phism class For 2 edges, there are two isomorphism classes, but they have neighbor of each vertex on C is not on C 9 Chapter 1: Fundamental Concepts Section 1.1: What Is a Graph? 10 Thus there are seven edges from v(C)to the remaining three vertices its neighbors. Since G has no cycle of length less than five, G is simple By the pigeonhole principle, one of the remaining vertices receives at least and any two neighbors of x are nonadjacent and have no common neighbor three of these edges. This vertex x not on C has three neighbors on C. other than x. Hence each E S-x has at least k-1 neighbors that For any three vertices on C, either two are adjacent or two have a common are not in S and not neighbors of any vertex in S. Hence g has at least neighbor on C (again the pigeonhole principle applies). Using x this com k(k-1)vertices outside S and at least k+ I vertices in S for at least k2+1 pletes a cycle of length at most 4. We have shown that the assumption of a altogether 7-cycle leads to a contradiction The 5-cycle achieves equality when k=2. For k=3, growing the graph Alternative completion of proof. let u be a vertex on C, and let u,w symmetrically from x permits completing the graph by adding edges among be the two vertices farthest from u on C. As argued earlier, no edges join the non-neighbors of x. The result is the Petersen graph.(Comment: For vertices ofC that are not consecutive on C. Thus u is not adjacent to v or w k >8. it is known that girth 5 with minimum degree k and exactly he for Hence u, u have a common neighbor off C, as do u, u. Since u has only one vertices is impossible, except for k= 7 and possibly for k=57. neighbor off C, these two common neighbors are the same. The resulting vertex x is adjacent to all of u, U, w, and now x, u, u is a 3-cycle 1.1.26. A k-regular graph of girth four has at least 2k vertices, with equality only for kkk. let g be k-regular of girth four, and chose xy EE(G). Girth 4 implies that G is simple and that x and y have no common neighbors Thus the neighborhoods N(r) and N()are disjoint sets of size k, which forces at least 2k vertices into G. Possibly there are others Note also that N(x) and N()are independent sets, since G has no triangle. If G has no vertices other than these, then the vertices in N(x) 1. 28. The Odd Graph has girth 6. The odd graph Ok is the disjointness can have neighbors only in N(y. Since G is k-regular, every vertex of N(r) graph of the set of k-element subsets of [2k+ 1] must be adjacent to every vertex of N(y). Thus G is isomorphic to Kk. k Vertices with a common neighbor correspond to k-sets with k-1 com with partite sets N(x) and N(y). In other words, there is only one such mon elements. Thus they have exactly one common neighbor, and Ok has isomorphism class for each value ofk no 4-cycle. Two vertices at distance 2 from a single vertex have at least Comment. One can also start with a vertex x, choose y from among k-2 common neighbors. For k>2, such vertices cannot be adjacent, and the k vertices in N(r), and observe that N(y)must have k-l more vertices thus Ok has no 5-cycle when k>2. To form a 6-cycle when k 22, let not in N(xUx. The proof then proceeds as above A={2,,k},B={k+2,,2k},a=1,b=k+1,C=2k+1.A6 cycle is (An alternative proof uses the methods of Section 1.3. a triangle-free A∪{a},B∪{b},A∪{c},B∪{a},A∪{b},BU{c} simple graph with n vertices has at most n /4 edges. Since g is k-regular The Odd Graph also is not bipartite. The successive elements this yields n/42 nk /2, and hence n2 2k. Furthermore, equality holds {1,,,k},+1,,2k},{2k+1,1,.,k-1}, ,{k+2,,…,2k+1} in the edge bound only for Kn/2.n/2, so this is the only such graph with 2k form an odd cycle vertices.(C. Pikscher)) 1.1. 29. Among any 6 people, there are 3 mutual acquaintances or 3 mutual strangers. Let g be the graph of the acquaintance relation, and let x be one of the people. Since x has 5 potential neighbors, x has at least 3 neighbors or at least 3 nonneighbors. By symmetry (if we complement G, we still have to prove the same statement), we may assume that x has at least 3 neighbors. If any pair of these people are acquainted then with x we have NI N(y)-{x} 3 mutual acquaintances but if no pair of neighbors ofx is acquainted, then 1. 27. A simple graph of girth 5 in which every vertex has degree at least the neighbors of x are three mutual strangers k has at least k2+1 vertices, with equality achieveable when k e 2, 3) .Let 1.1.30. The number of edges incident to u; is the ith diagonal entry in MM g be k-regular of girth five. Let s be the set consisting of a vertex x and and in a. In both MM and A' this is the sum of the squares of the entries 11 Chapter 1: Fundamental Concepts Section 1.1: What Is a graph? 12 in the ith row. For MM, this follows immediately from the definition of matrix multiplication and transposition, but for A" this uses the graph- H H H H theoretic fact that a=A i.e. column i is the same as row i. because G is simple, the entries of the matrix are allo or l, so the sum of the squares in a row equals the number of ls in the row. In m, the ls in a row denote incident edges; in A they denote vertex neighbors. In either case, the number of ls is the degree of the vertex. H H H ifitj, then the entry in position (i, j) of a is the number of common neighbors of vi and vj. The matrix multiplication puts into position(i, J the"product" row i and column j; that is kala;, aK, When G is simple, entries in A are 1 or 0, depending on whether the corresponding vertices tlo forn=4k+1, we add a vertex x to the graph constructed above. Join x to the 2k vertices in X1 and X4 to form G. The isomorphism showing that are adjacent. Hence ai. kak, i= 1 if Uk is a common neighbor of v; and u G-x is self-complementary also works for G(with x mapped to itself) otherwise. the contribution is 0. Thus the number of contributions of 1 to since this isomorphism maps NG(x)=X1U X to N(x)=X2UX3 entry(i, j)is the number of common neighbos of vi and vi Proof 2 (inductive construction). If G is self-complementary, then let Ifitj, then the entry in position(i,) of MM is the number of edges Hi be the graph obtained from G and P4 by joining the two ends of p4 to Joining vi and vi(0 or 1 when G has no multiple edges). The ith row of all vertices of G. Let H2 be the graph obtained from G and Pa by join M has 1s corresponding to the edges incident to vi. The jth column of ing the two center vertices of P4 to all vertices of G. Both H1 and H2 M is the same as the jth row of M, which has 1s corresponding to the are self-complementary. Using this with G= K1 produces the two self- edges incident to v;. Summing the products of corresponding entries will complementary graphs of order 5, namely Cs and the bull contribute 1 for each edge incident to both u; and vi; 0 otherwise Self-complementary graphs with order divisible by 4 arise from re- Comment. For graphs without loops, both arguments for(i, j) in gen peated use of the above using g= Pa as a starting point and self- eral apply when i=j to explain the diagonal entries complementary graphs of order congruent to 1 modulo 4 arise from repeated use of the above using G= Ki as a starting point. This construction pro- 1.1.31. Kn decomposes into two isomorphic ("self-complementary) sub duces many more self-complementary graphs than the explicit construction graphs if and only if n or n-1 is divisible by 4 in Proof 1 a) The number of vertices in a self-complementary graph is congruent to 0 or 1(mod 4). If G and G are isomorphic, then they have the same I.1.32. Km n decomposes into two isomorphic subgraphs if and only if m number of edges, but together they have()edges(with none repeated), so and n are not both odd. The condition is necessary because the number the number of edges in each must be n(n-1)/4. Since this is an integer of edges must be even. It is sufficient because Km.n decomposes into two and the numbers n and n-1 are not both even, one of in, n-1 must be copies of Kmn/2 when n is even divisible by 4 b)Construction of self-complementary graphs for all such n 1.1.33. Decomposition of complete graphs into cycles through all vertices Proof 1(explicit construction). We generalize the structure of the View the vertex set of K, as Zn, the values 0, .., n-1 in cyclic order. Since self-complementary graphs on 4 and 5 vertices, which are P4 and Cs. For each vertex has degree n-1 and each cycle uses two edges at each vertex take four vertex sets of size k, say X1, X2, X3, X, and Join all the decomposition has(n-1)/2 cycles vertices of X, to those of X; +1, for i= 1, 2, 3. To specify the rest of G, within For n=5 and n=7, it suffices to use cycles formed by traversing the these sets let X1 and X4 induce copies of a graph h with k vertices, and let vertices with constant difference:(0, 1, 2, 3, 4)and(0. 2, 4, 1, 3) for n= 5 X2 and Xs induce H. (For example, H may be Kk )In G, both X2 and X and(0,1,2,3,4,5,6),(0,2,4,6,1,3.5),and(0,3,6,2,5,1,4)forn=7. induce I, while X1 and X4 induce I, and the connections between sets are This construction fails for n=9 since the edges with difference 3 form X2分X4分X1分X. Thus relabeling the subsets defines an isomorphism three 3-cycles. The cyclically symmetric construction below treats the ver- between G and G. (There are still other constructions for G) tex set as Zs together with one special vertex.

...展开详情

评论 下载该资源后可以进行评论 3

qq_17319783 图论导引第二版英文版答案
2019-04-08
回复
cly19960326 挺不错的资料
2017-09-21
回复
bian12252008 我是第一个下载的吗?不管怎样,这本答案很赞!!!
2015-01-21
回复
img
lion003

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐