Skip to content
Textbook Guides

Solution Manual for Introduction to Graph Theory, 2nd Edition

Find clear solutions to every textbook problem with Solution Manual for Introduction to Graph Theory, 2nd Edition, your essential resource for textbook answers.

Preview 16 of 512 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    i INTRODUCTION TO GRAPH THEORY SECOND EDITION (2001) SOLUTION MANUAL SUMMER 2005 VERSION DOUGLAS B. WEST MATHEMATICS DEPARTMENT UNIVERSITY OF ILLINOIS

  2. Page 2
  3. Page 3
    Read page 3 as text

    1 Chapter 1: Fundamental Concepts 1.FUNDAMENTAL CONCEPTS 1.1. WHAT IS A GRAPH? 1.1.1. Complete bipartite graphs and complete graphs. The complete bipar- tite graph K m , n is a complete graph if and only if m = n = 1 or { m , n } = { 1 , 0 } . 1.1.2. Adjacency matrices and incidence matrices for a 3-vertex path. ( 0 1 1 1 0 0 1 0 0 ) ( 0 1 0 1 0 1 0 1 0 ) ( 0 0 1 0 0 1 1 1 0 ) ( 1 1 1 0 0 1 ) ( 1 1 0 1 1 0 ) ( 1 0 1 1 0 1 ) ( 0 1 1 1 1 0 ) ( 1 0 0 1 1 1 ) ( 0 1 1 0 1 1 ) Adjacency matrices for a path and a cycle with six vertices.       0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0             0 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 1 0 0 0 1 0       1.1.3. Adjacency matrix for K m , n . m n m 0 1 n 1 0 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 hence f preserves non-adjacency and adjacency in G and is an isomor- phism from G to H . The same argument applies for the converse, since the complement of G is G .

  4. Page 4
    Read page 4 as text

    Section 1.1: What Is a Graph? 2 1.1.5. If every 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. (If infinite graphs are allowed, then the graph can be an infinite path.) 1.1.6. The graph below decomposes into copies of P 4 . • • • • • • 1.1.7. A graph with more than six vertices of odd degree cannot be decom- 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 endpoints. 1.1.8. Decompositions of a graph. The graph below decomposes into copies of K 1 , 3 with centers at the marked vertices. It decomposes into bold and solid copies of P 4 as shown. • • • • • • • • 1.1.9. A graph and its complement. With vertices labeled as shown, two vertices are adjacent in the graph on the right if and only if they are not adjacent in the graph on the left. • • • • • • • • a b c d e f g h • • • • • • • • a f d g c h b e 1.1.10. The complement of a simple disconnected graph must be connected— TRUE. A disconnected graph G has vertices x , y that do not belong to a path. Hence x and y are adjacent in G . Furthermore, x and y have no com- mon neighbor in G , since that would yield a path connecting them. Hence

  5. Page 5
    Read page 5 as text

    3 Chapter 1: Fundamental Concepts every vertex not in { x , y } is adjacent in G to at least one of { x , y } . Hence every vertex can reach every other vertex in G using paths through { x , y } . 1.1.11. Maximum clique and maximum independent set. Since two ver- tices have degree 3 and there are only four other vertices, there is no clique of size 5. A complete subgraph with four vertices is shown in bold. Since two vertices are adjacent to all others, an independent set con- taining either of them has only one vertex. Deleting them leaves P 4 , in which the maximum size of an independent set is two, as marked. • • • • • • 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. The vertices 12 , 13 , 14 , 15 form an independent set of size 4, since any two of these vertices have 1 as a common element and hence are nonadja- cent. Visually, there is an independent set of size 4 marked on the drawing 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 , b ∈ [5]. We show that S has at most three additional vertices. The vertices not adjacent to ab are ac , bd , ae , bc , ad , be , and they form a cycle in that order. Hence at most half of them can be added to S . 1.1.13. The graph with vertex set { 0 , 1 } k and x ↔ y when x and y differ in one place is bipartite. The partite sets are determined by the parity of the number of 1’s. Adjacent vertices have opposite parity. (This graph is the k -dimensional hypercube; see Section 1.3.) 1.1.14. Cutting opposite corner squares from an eight by eight checkerboard leaves a subboard that cannot be partitioned into rectangles consisting of two adjacent unit squares. 2-coloring the squares of a checkerboard so that adjacent squares have opposite colors shows that the graph having a vertex for each square and an edge for each pair of adjacent squares is bipartite. The squares at opposite corners have the same color; when these are deleted, there are 30 squares of that color and 32 of the other

  6. Page 6
    Read page 6 as text

    Section 1.1: What Is a Graph? 4 color. Each pair of adjacent squares has one of each color, so the remaining squares cannot be partitioned into sets of this type. Generalization: the two partite sets of a bipartite graph cannot be matched up using pairwise-disjoint edges if the two partite sets have un- equal sizes. 1.1.15. Common graphs in four families: A = { paths } , B = { cycles } , C = { complete graphs } , D = { bipartite graphs } . A ∩ B = ∅ : In a cycle, the numbers of vertices and edges are equal, but this is false for a path. A ∩ C = { K 1 , K 2 } : To be a path, a graph must contain no cycle. A ∩ D = A : non-bipartite graphs have odd cycles. B ∩ C = K 3 : Only when n = 3 does ( n 2 ) = n . B ∩ D = { C 2 k : k ≥ 2 } : odd cycles are not bipartite. C ∩ D = { K 1 , K 2 } : bipartite graphs cannot have triangles. 1.1.16. The graphs below are not isomorphic. The graph on the left has four cliques of size 4, and the graph on the right has only two. Alternatively, the complement of the graph on the left is disconnected (two 4-cycles), while the complement of the graph on the right is connected (one 8-cycle). • • • • • • • • • • • • • • • • 1.1.17. There are exactly two isomorphism classes of 4-regular simple 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- phism φ : V ( G ) → V ( H ) is also an isomorphism from G to H , and vice versa. Hence it suffices to count the isomorphism classes of 2-regular sim- ple graphs with 7 vertices. Every component of a finite 2-regular graph is a cycle. In a simple graph, each cycle has at least three vertices. Hence each 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 C 7 and C 3 + C 4 – a single cycle or two cycles of lengths three and four. 1.1.18. Isomorphism. Using the correspondence indicated below, the first two graphs are isomorphic; the graphs are bipartite, with u i ↔ v j if and only if i 6 = j . The third graph contains odd cycles and hence is not isomor- phic to the others.

  7. Page 7
    Read page 7 as text

    5 Chapter 1: Fundamental Concepts • • • • • • • • v 2 u 4 v 3 u 1 u 3 v 1 u 2 v 4 • • • • • • • • u 4 u 3 u 2 u 1 v 4 v 3 v 2 v 1 • • • • • • • • Visually, the first two graphs are Q 3 and the graph obtained by delet- ing four disjoint edges from K 4 , 4 . In Q 3 , each vertex is adjacent to the vertices whose names have opposite parity of the number of 1s, except for the complementary vertex. Hence Q 3 also has the structure of K 4 , 4 with four disjoint edges deleted; this proves isomorphism without specifying an explicit bijection. 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. The graph on the left is bipartite, as shown by marking one partite set. It cannot be isomorphic to the others, since they contain 5-cycles. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 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 ( F ) to V ( H ) that preserves the adjacency relation). To do this, we name the vertices of F , write the name of each vertex of F on the corresponding vertex in H , and show that the names of the edges are the same in H and F . This proves that H is a way to redraw F . We have done this below using the first eight letters and the first eight natural numbers as names. To prove quickly that the adjacency relation is preserved, observe that 1 , a , 2 , b , 3 , c , 4 , d , 5 , e , 6 , f , 7 , g , 8 , h is a cycle in both drawings, and the ad- ditional edges 1 c , 2 d , 3 e , 4 f , 5 g , 6 h , 7 a , 8 b are also the same in both draw- ings. Thus the two graphs have the same edges under this vertex corre- spondence. Equivalently, if we list the vertices in this specified order for

  8. Page 8
    Read page 8 as text

    Section 1.1: What Is a Graph? 6 the two drawings, the two adjacency matrices are the same, but that is harder to verify. G is not isomorphic to F or to H . In F and in H , the numbers form an independent set, as do the letters. Thus F and H are bipartite. The graph 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 do not, but it is harder to prove the absence of a 4-cycle than to prove the absence of an odd cycle. • • • • • • • • h 2 f 8 d 6 b 4 • • • • • • • • 1 a 7 g 5 e 3 c • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 1 1.1.21. Isomorphism. Both graphs are bipartite, as shown below by mark- ing one partite set. In the graph on the right, every vertex appears in 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. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 1.1.22. Isomorphism of explicit graphs. Among the graphs below, { G 1 , G 2 , G 5 } are pairwise isomorphic. Also G 3 ∼ = G 4 , and these are not isomorphic to any of the others. Thus there are exactly two isomorphism classes represented among these graphs. To prove these statements, one can present explicit bijections between vertex sets and verify that these preserve the adjacency relation (such as by displaying the adjacency matrix, for example). One can also make other structural arguments. For example, one can move the highest vertex in G 3 down into the middle of the picture to obtain G 4 ; from this one can list the desired bijection.

  9. Page 9
    Read page 9 as text

    7 Chapter 1: Fundamental Concepts One can also recall that two graphs are isomorphic if and only if their complements are isomorphic. The complements of G 1 , G 2 , and G 5 are cy- cles of length 7, which are pairwise isomorphic. Each of G 3 and G 4 consists of two components that are cycles of lengths 3 and 4; these graphs are isomorphic to each other but not to a 7-cycle. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • G 1 G 2 G 3 G 4 G 5 1.1.23. Smallest pairs of nonisomorphic graphs with the same vertex de- grees. For multigraphs, loopless multigraphs, and simple graphs, the re- quired numbers of vertices are 2,4,5; constructions for the upper bounds appear below. We must prove that these constructions are smallest. • • • • • • • • • • • • • • • • • • • • • • a) general b) loopless c) simple a) With 1 vertex, every edge is a loop, and the isomorphism class is determined by the number of edges, which is determined by the vertex degree. Hence nonisomorphic graphs with the same vertex degrees have at least two vertices. b) Every loopless graph is a graph, so the answer for loopless graphs is at least 2. The isomorphism class of a loopless graph with two vertices 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 degrees be a , b , c , and let the multiplicities of the opposite edges be x , y , z , where Since a = y + z , b = x + z , and c = x + y , we can solve for the multiplicities in terms of the degrees by x = ( b + c − a )/ 2, y = ( a + c − b )/ 2, and z = ( a + b − c )/ 2. Hence the multiplicities are determined by the degrees, and all loopless graphs with vertex degrees a , b , c are pairwise isomorphic. Hence nonisomorphic loopless graphs with the same vertex degrees have at least four vertices. c) Since a simple graph is a loopless graph, the answer for simple graphs is at least 4. There are 11 isomorphism classes of simple graphs with four vertices. For each of 0,1,5, or 6 edges, there is only one isomor- phism class. For 2 edges, there are two isomorphism classes, but they have

  10. Page 10
    Read page 10 as text

    Section 1.1: What Is a Graph? 8 different lists of vertex degrees (similarly for 4 edges). For 3 edges, the three isomorphism classes have degree lists 3111, 2220, and 2211, all dif- ferent. Hence nonisomorphic simple graphs with the same vertex degrees must have at least five vertices. 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 columns of the adjacency matrices to make them identical. The various drawings of the Petersen graph below illustrate its symmetries; the label- ings indicate that these are all “the same” (unlabeled) graph. The number of isomorphisms from one graph to another is the same as the number of isomorphisms from the graph to itself. • • • • • • • • • • 45 12 23 13 51 34 52 41 35 24 • • • • • • • • • • 12 52 23 35 13 51 34 41 24 45 • • • • • • • • • • 51 24 41 35 12 34 52 13 45 23 • • • • • • • • • • 12 34 52 13 24 51 23 41 35 45 1.1.25. The Petersen graph has no cycle of length 7. Suppose that the Pe- tersen graph has a cycle C of length 7. Since any two vertices of C are connected by a path of length at most 3 on C , any additional edge with endpoints on C would create a cycle of length at most 4. Hence the third neighbor of each vertex on C is not on C .

  11. Page 11
    Read page 11 as text

    9 Chapter 1: Fundamental Concepts Thus there are seven edges from V ( C ) to the remaining three vertices. By the pigeonhole principle, one of the remaining vertices receives at least three of these edges. This vertex x not on C has three neighbors on C . For any three vertices on C , either two are adjacent or two have a common neighbor on C (again the pigeonhole principle applies). Using x , this com- pletes a cycle of length at most 4. We have shown that the assumption of a 7-cycle leads to a contradiction. Alternative completion of proof. Let u be a vertex on C , and let v, w be the two vertices farthest from u on C . As argued earlier, no edges join vertices of C that are not consecutive on C . Thus u is not adjacent to v or w . Hence u , v have a common neighbor off C , as do u , w . Since u has only one neighbor off C , these two common neighbors are the same. The resulting vertex x is adjacent to all of u , v, w , and now x , v, w is a 3-cycle. 1.1.26. A k -regular graph of girth four has at least 2 k vertices, with equality only for K k , k . Let G be k -regular of girth four, and chose x y ∈ E ( G ) . Girth 4 implies that G is simple and that x and y have no common neighbors. Thus the neighborhoods N ( x ) and N ( y ) are disjoint sets of size k , which forces at least 2 k vertices into G . Possibly there are others. Note also that N ( x ) and N ( y ) are independent sets, since G has no triangle. If G has no vertices other than these, then the vertices in N ( x ) can have neighbors only in N ( y ) . Since G is k -regular, every vertex of N ( x ) must be adjacent to every vertex of N ( y ) . Thus G is isomorphic to K k , k , with partite sets N ( x ) and N ( y ) . In other words, there is only one such isomorphism class for each value of k . Comment. One can also start with a vertex x , choose y from among the k vertices in N ( x ) , and observe that N ( y ) must have k − 1 more vertices not in N ( x ) ∪ { x } . The proof then proceeds as above. (An alternative proof uses the methods of Section 1.3. A triangle-free simple graph with n vertices has at most n 2 / 4 edges. Since G is k -regular, this yields n 2 / 4 ≥ nk / 2, and hence n ≥ 2 k . Furthermore, equality holds in the edge bound only for K n / 2 , n / 2 , so this is the only such graph with 2 k vertices. (C. Pikscher)) • • • • • N ( x ) − { y } x N ( y ) − { x } • • • • • y 1.1.27. A simple graph of girth 5 in which every vertex has degree at least k has at least k 2 + 1 vertices, with equality achieveable when k ∈ { 2 , 3 } . Let G be k -regular of girth five. Let S be the set consisting of a vertex x and

  12. Page 12
    Read page 12 as text

    Section 1.1: What Is a Graph? 10 its neighbors. Since G has no cycle of length less than five, G is simple, and any two neighbors of x are nonadjacent and have no common neighbor other than x . Hence each y ∈ S − { x } has at least k − 1 neighbors that are not in S and not neighbors of any vertex in S . Hence G has at least k ( k − 1 ) vertices outside S and at least k + 1 vertices in S for at least k 2 + 1 altogether. The 5-cycle achieves equality when k = 2. For k = 3, growing the graph symmetrically from x permits completing the graph by adding edges among the non-neighbors of x . The result is the Petersen graph. (Comment: For k > 3, it is known that girth 5 with minimum degree k and exactly k 2 + 1 vertices is impossible, except for k = 7 and possibly for k = 57.) • • • • • • • • • • x 1.1.28. The Odd Graph has girth 6. The Odd Graph O k is the disjointness graph of the set of k -element subsets of [2 k + 1]. Vertices with a common neighbor correspond to k -sets with k − 1 com- mon elements. Thus they have exactly one common neighbor, and O k has no 4-cycle. Two vertices at distance 2 from a single vertex have at least k − 2 common neighbors. For k > 2, such vertices cannot be adjacent, and thus O k has no 5-cycle when k > 2. To form a 6-cycle when k ≥ 2, let A = { 2 , . . . , k } , B = { k + 2 , . . . , 2 k } , a = 1, b = k + 1, c = 2 k + 1. A 6-cycle is A ∪ { a } , B ∪ { b } , A ∪ { c } , B ∪ { a } , A ∪ { b } , B ∪ { c } . The Odd Graph also is not bipartite. The successive elements { 1 , . . . , k } , { k + 1 , . . . , 2 k } , { 2 k + 1 , 1 , . . . , k − 1 } , . . ., { k + 2 , . . . , 2 k + 1 } form an odd cycle. 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 3 mutual acquaintances, but if no pair of neighbors of x is acquainted, then the neighbors of x are three mutual strangers. 1.1.30. The number of edges incident to v i is the i th diagonal entry in M M T and in A 2 . In both M M T and A 2 this is the sum of the squares of the entries

  13. Page 13
    Read page 13 as text

    11 Chapter 1: Fundamental Concepts in the i th row. For M M T , this follows immediately from the definition of matrix multiplication and transposition, but for A 2 this uses the graph- theoretic fact that A = A T ; i.e. column i is the same as row i . Because G is simple, the entries of the matrix are all 0 or 1, so the sum of the squares in a row equals the number of 1s in the row. In M , the 1s in a row denote incident edges; in A they denote vertex neighbors. In either case, the number of 1s is the degree of the vertex. If i 6 = j , then the entry in position ( i , j ) of A 2 is the number of common neighbors of v i and v j . The matrix multiplication puts into position ( i , j ) the “product” of row i and column j ; that is ∑ n k = 1 a i , k a k , j . When G is simple, entries in A are 1 or 0, depending on whether the corresponding vertices are adjacent. Hence a i , k a k , j = 1 if v k is a common neighbor of v i and v j ; otherwise, the contribution is 0. Thus the number of contributions of 1 to entry ( i , j ) is the number of common neighbos of v i and v j . If i 6 = j , then the entry in position ( i , j ) of M M T is the number of edges joining v i and v j (0 or 1 when G has no multiple edges). The i th row of M has 1s corresponding to the edges incident to v i . The j th column of M T is the same as the j th row of M , which has 1s corresponding to the edges incident to v j . Summing the products of corresponding entries will contribute 1 for each edge incident to both v i and v j ; 0 otherwise. Comment. For graphs without loops, both arguments for ( i , j ) in gen- eral apply when i = j to explain the diagonal entries. 1.1.31. K n decomposes into two isomorphic (“self-complementary”) sub- graphs if and only if n or n − 1 is divisible by 4. 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 number of edges, but together they have ( n 2 ) edges (with none repeated), so the number of edges in each must be n ( n − 1 )/ 4. Since this is an integer and the numbers n and n − 1 are not both even, one of { n , n − 1 } must be divisible by 4. b) Construction of self-complementary graphs for all such n . Proof 1 (explicit construction). We generalize the structure of the self-complementary graphs on 4 and 5 vertices, which are P 4 and C 5 . For n = 4 k , take four vertex sets of size k , say X 1 , X 2 , X 3 , X 4 , and join all vertices of X i to those of X i + 1 , for i = 1 , 2 , 3. To specify the rest of G , within these sets let X 1 and X 4 induce copies of a graph H with k vertices, and let X 2 and X 3 induce H . (For example, H may be K k .) In G , both X 2 and X 3 induce H , while X 1 and X 4 induce H , and the connections between sets are X 2 ↔ X 4 ↔ X 1 ↔ X 3 . Thus relabeling the subsets defines an isomorphism between G and G . (There are still other constructions for G .)

  14. Page 14
    Read page 14 as text

    Section 1.1: What Is a Graph? 12 H H H H H H H H For n = 4 k + 1, we add a vertex x to the graph constructed above. Join x to the 2 k vertices in X 1 and X 4 to form G . The isomorphism showing that G − x is self-complementary also works for G (with x mapped to itself), since this isomorphism maps N G ( x ) = X 1 ∪ X 4 to N G ( x ) = X 2 ∪ X 3 . Proof 2 (inductive construction). If G is self-complementary, then let H 1 be the graph obtained from G and P 4 by joining the two ends of P 4 to all vertices of G . Let H 2 be the graph obtained from G and P 4 by join- ing the two center vertices of P 4 to all vertices of G . Both H 1 and H 2 are self-complementary. Using this with G = K 1 produces the two self- complementary graphs of order 5, namely C 5 and the bull. Self-complementary graphs with order divisible by 4 arise from re- peated use of the above using G = P 4 as a starting point, and self- complementary graphs of order congruent to 1 modulo 4 arise from repeated use of the above using G = K 1 as a starting point. This construction pro- duces many more self-complementary graphs than the explicit construction in Proof 1. 1.1.32. K m , n decomposes into two isomorphic subgraphs if and only if m and n are not both odd. The condition is necessary because the number of edges must be even. It is sufficient because K m , n decomposes into two copies of K m , n / 2 when n is even. 1.1.33. Decomposition of complete graphs into cycles through all vertices. View the vertex set of K n as Z n , the values 0 , . . . , n − 1 in cyclic order. Since each vertex has degree n − 1 and each cycle uses two edges at each vertex, the decomposition has ( n − 1 )/ 2 cycles. For n = 5 and n = 7, it suffices to use cycles formed by traversing the vertices with constant difference: ( 0 , 1 , 2 , 3 , 4 ) and ( 0 , 2 , 4 , 1 , 3 ) for n = 5 and ( 0 , 1 , 2 , 3 , 4 , 5 , 6 ) , ( 0 , 2 , 4 , 6 , 1 , 3 , 5 ) , and ( 0 , 3 , 6 , 2 , 5 , 1 , 4 ) for n = 7. This construction fails for n = 9 since the edges with difference 3 form three 3-cycles. The cyclically symmetric construction below treats the ver- tex set as Z 8 together with one special vertex.

  15. Page 15
    Read page 15 as text

    13 Chapter 1: Fundamental Concepts • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 1.1.34. Decomposition of the Petersen graph into copies of P 4 . Consider the drawing of the Petersen graph with an inner 5-cycle and outer 5-cycle. Each P 4 consists of one edge from each cycle and one cross edge joining them. Extend each cross edge e to a copy of P 4 by taking the edge on each of the two 5-cycles that goes in a clockwise direction from e . In this way, the edges on the outside 5-cycle are used in distinct copies of P 4 , and the same holds for the edges on the inside 5-cycle. Decomposition of the Petersen graph into three pairwise-isomorphic connected subgraphs. Three such decompositions are shown below. We re- stricted the search by seeking a decomposition that is unchanged by 120 ◦ rotations in a drawing of the Petersen graph with 3-fold rotational symme- try. The edges in this drawing form classes of size 3 that are unchanged under rotations of 120 ◦ ; each subgraph in the decomposition uses exactly one edge from each class. • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 1.1.35. K n decomposes into three pairwise-isomorphic subgraphs if and only if n + 1 is not divisible by 3. The number of edges is n ( n − 1 )/ 2. If n + 1 is divisible by 3, then n and n − 1 are not divisible by 3. Thus decomposition into three subgraphs of equal size is impossible in this case. If n + 1 is not divisible by 3, then e ( K n ) is divisible by 3, since n or n − 1 is divisible by 3. We construct a decomposition into three subgraphs that are pairwise isomorphic (there are many such decompositions). When n is a multiple of 3, we partition the vertex set into three subsets V 1 , V 2 , V 3 of equal size. Edges now have two types: within a set or joining two sets. Let the i th subgraph G i consist of all the edges within V i and all the edges joining the two other subsets. Each edge of K n appears in exactly

  16. Page 16
    Read page 16 as text

    Section 1.1: What Is a Graph? 14 one of these subgraphs, and each G i is isomorphic to the disjoint union of K n / 3 and K n / 3 , n / 3 . When n ≡ 1 ( mod 3 ) , consider one vertex w . Since n − 1 is a multiple of 3, we can form the subgraphs G i as above on the remaining n − 1 ver- tices. Modify G i to form H i by joining w to every vertex of V i . Each edge involving w has been added to exactly one of the three subgraphs. Each H i is isomorphic to the disjoint union of K 1 + ( n − 1 )/ 3 and K ( n − 1 )/ 3 ,( n − 1 )/ 3 . • 1.1.36. If K n decomposes into triangles, then n − 1 or n − 3 is divisible by 6. Such a decomposition requires that the degree of each vertex is even and the number of edges is divisible by 3. To have even degree, n must be odd. Also n ( n − 1 )/ 2 is a multiple of 3, so 3 divides n or n − 1. If 3 divides n and n is odd, then n − 3 is divisible by 6. If 3 divides n − 1 and n is odd, then n − 1 is divisible by 6. 1.1.37. A graph in which every vertex has degree 3 has no decomposition into paths with at least five vertices each. Suppose that G has such a de- composition. Since every vertex has degree 3, each vertex is an endpoint of at least one of the paths and is an internal vertex on at most one of them. Since every path in the decomposition has two endpoints and has at least three internal vertices, we conclude that the number of paths in the decomposition is at least n ( G )/ 2 and is at most n ( G )/ 3, which is impossible. Alternatively, let k be the number of paths. There are 2 k endpoints of paths. On the other hand, since each internal vertex on a path in the de- composition must be an endpoint of some other path in the decomposition, there must be at least 3 k endpoints of paths. The contradiction implies that there cannot be such a decomposition. 1.1.38. A 3-regular graph G has a decomposition into claws if and only if G is bipartite. When G is bipartite, we produce a decomposition into claws. We use all claws obtained by taking the three edges incident with a single vertex in the first partite set. Each claw uses all the edges incident to its central vertex. Since each edge has exactly one endpoint in the first partite set, each edge appears in exactly one of these claws. When G has a decomposition into claws, we partition V ( G ) into two independent sets. Let X be the set of centers of the claws in the decom- position. Since every vertex has degree 3, each claw in the decomposition

496 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Mathematics study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.