Solution Manual for Introduction to Graph Theory, 2nd Edition

Preview (16 of 512 Pages)

100%

Purchase to unlock

Loading page image...

iINTRODUCTION TO GRAPH THEORYSECOND EDITION (2001)SOLUTION MANUALSUMMER 2005 VERSIONDOUGLAS B. WESTMATHEMATICS DEPARTMENTUNIVERSITY OF ILLINOIS

Loading page image...

1Chapter 1: Fundamental Concepts1.FUNDAMENTAL CONCEPTS1.1. WHAT IS A GRAPH?1.1.1.Complete bipartite graphs and complete graphs.The complete bipar-tite graphKm,nis a complete graph if and only ifm=n=1 or{m,n} = {1,0}.1.1.2.Adjacency matrices and incidence matrices for a 3-vertex path.(011100100) (010101010) (001001110)(111001) (110110) (101101) (011110) (100111) (011011)Adjacency matrices for a path and a cycle with six vertices.0100001010000101000010100001010000100100011010000101000010100001011000101.1.3.Adjacency matrix forKm,n.mnm01n101.1.4.G∼=Hif and only ifG∼=H.Iffis an isomorphism fromGtoH,thenfis a vertex bijection preserving adjacency and nonadjacency, andhencefpreserves non-adjacency and adjacency inGand is an isomor-phism fromGtoH. The same argument applies for the converse, since thecomplement ofGisG.

Loading page image...

Section 1.1: What Is a Graph?21.1.5.If every vertex of a graphGhas degree 2, thenGis a cycle—FALSE.Such a graph can be a disconnected graph with each component a cycle. (Ifinfinite graphs are allowed, then the graph can be an infinite path.)1.1.6.The graph below decomposes into copies ofP4.••••••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 endpointof some path in a decomposition into paths.Three paths have only sixendpoints.1.1.8.Decompositions of a graph.The graph below decomposes into copiesofK1,3with centers at the marked vertices.It decomposes into bold andsolid copies ofP4as shown.••••••••1.1.9.A graph and its complement.With vertices labeled as shown, twovertices are adjacent in the graph on the right if and only if they are notadjacent in the graph on the left.••••••••abcdefgh••••••••afdgchbe1.1.10.The complement of a simple disconnected graph must be connected—TRUE.A disconnected graphGhas verticesx,ythat do not belong to apath. Hencexandyare adjacent inG. Furthermore,xandyhave no com-mon neighbor inG, since that would yield a path connecting them. Hence

Loading page image...

3Chapter 1: Fundamental Conceptsevery vertex not in{x,y}is adjacent inGto at least one of{x,y}. Henceevery vertex can reach every other vertex inGusing 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 cliqueof 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 leavesP4, inwhich the maximum size of an independent set is two, as marked.••••••1.1.12.The Petersen graph.The Petersen graph contains odd cycles, so itis 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 anytwo 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 drawingof the Petersen graph on the cover of the book.There are many ways toshow that the graph has no larger independent set.Proof 1. Two consecutive vertices on a cycle cannot both appear in anindependent set, so every cycle contributes at most half its vertices. Sincethe vertex set is covered by two disjoint 5-cycles, every independent set hassize at most 4.Proof 2. Letabbe a vertex in an independent setS, wherea,b∈[5].We show thatShas at most three additional vertices.The vertices notadjacent toabareac,bd,ae,bc,ad,be, and they form a cycle in that order.Hence at most half of them can be added toS.1.1.13.The graph with vertex set{0,1}kandx↔ywhenxandydiffer inone place is bipartite.The partite sets are determined by the parity of thenumber of 1’s. Adjacent vertices have opposite parity. (This graph is thek-dimensional hypercube; see Section 1.3.)1.1.14.Cutting opposite corner squares from an eight by eight checkerboardleaves a subboard that cannot be partitioned into rectangles consisting oftwo adjacent unit squares.2-coloring the squares of a checkerboard sothat adjacent squares have opposite colors shows that the graph havinga vertex for each square and an edge for each pair of adjacent squaresis bipartite.The squares at opposite corners have the same color; whenthese are deleted, there are 30 squares of that color and 32 of the other

Loading page image...

Section 1.1: What Is a Graph?4color. Each pair of adjacent squares has one of each color, so the remainingsquares cannot be partitioned into sets of this type.Generalization:the two partite sets of a bipartite graph cannot bematched 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= {K1,K2}: To be a path, a graph must contain no cycle.A∩D=A: non-bipartite graphs have odd cycles.B∩C=K3: Only whenn=3 does(n2)=n.B∩D= {C2k:k≥2}: odd cycles are not bipartite.C∩D= {K1,K2}: bipartite graphs cannot have triangles.1.1.16.The graphs below are not isomorphic.The graph on the left has fourcliques of size 4, and the graph on the right has only two. Alternatively, thecomplement of the graph on the left is disconnected (two 4-cycles), whilethe complement of the graph on the right is connected (one 8-cycle).••••••••••••••••1.1.17.There are exactly two isomorphism classes of 4-regular simplegraphs with 7 vertices.Simple graphsGandHare isomorphic if andonly if their complementsGandHare isomorphic, because an isomor-phismφ:V(G)→V(H)is also an isomorphism fromGtoH, and viceversa. 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 acycle. In a simple graph, each cycle has at least three vertices. Hence eachclass it determined by partitioning 7 into integers of size at least 3 to bethe sizes of the cycles. The only two graphs that result areC7andC3+C4– a single cycle or two cycles of lengths three and four.1.1.18.Isomorphism.Using the correspondence indicated below, the firsttwo graphs are isomorphic; the graphs are bipartite, withui↔vjif andonly ifi6=j. The third graph contains odd cycles and hence is not isomor-phic to the others.

Loading page image...

5Chapter 1: Fundamental Concepts••••••••v2u4v3u1u3v1u2v4••••••••u4u3u2u1v4v3v2v1••••••••Visually, the first two graphs areQ3and the graph obtained by delet-ing four disjoint edges fromK4,4.InQ3, each vertex is adjacent to thevertices whose names have opposite parity of the number of 1s, except forthe complementary vertex. HenceQ3also has the structure ofK4,4withfour disjoint edges deleted; this proves isomorphism without specifying anexplicit 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 theintermediate ring in the second graph. Pulling one of the inner 5-cycles ofthe rightmost graph out to the outside transforms the graph into the samedrawing 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.FandHare isomorphic.We exhibit an isomorphism (a bijection fromV(F)toV(H)that preserves the adjacency relation). To do this, we namethe vertices ofF, write the name of each vertex ofFon the correspondingvertex inH, and show that the names of the edges are the same inHandF. This proves thatHis a way to redrawF. We have done this below usingthe first eight letters and the first eight natural numbers as names.To prove quickly that the adjacency relation is preserved, observe that1,a,2,b,3,c,4,d,5,e,6,f,7,g,8,his a cycle in both drawings, and the ad-ditional edges 1c,2d,3e,4f,5g,6h,7a,8bare 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

Loading page image...

Section 1.1: What Is a Graph?6the two drawings, the two adjacency matrices are the same, but that isharder to verify.Gis not isomorphic toFor toH.InFand inH, the numbers form anindependent set, as do the letters. ThusFandHare bipartite. The graphGcannot be bipartite, since it contains an odd cycle.The vertices abovethe 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 othersdo not, but it is harder to prove the absence of a 4-cycle than to prove theabsence of an odd cycle.••••••••h2f8d6b4••••••••1a7g5e3c••••••••••••••••••••• •••• •••••••a2b3c4d5e6f7g8h11.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 ineight 4-cycles.In the graph on the left, every vertex appears in only six4-cycles (it is enough just to check one).Thus they are not isomorphic.Alternatively, for every vertex in the right graph there are five verticeshaving common neighbors with it, while in the left graph there are sixsuch vertices.••••••••••••••••••••••••• •••••••1.1.22.Isomorphismofexplicitgraphs.Amongthegraphsbelow,{G1,G2,G5}are pairwise isomorphic.AlsoG3∼=G4, and these are notisomorphic to any of the others. Thus there are exactly two isomorphismclasses represented among these graphs.To prove these statements, one can present explicit bijections betweenvertex sets and verify that these preserve the adjacency relation (such asby displaying the adjacency matrix, for example). One can also make otherstructural arguments. For example, one can move the highest vertex inG3down into the middle of the picture to obtainG4; from this one can list thedesired bijection.

Loading page image...

7Chapter 1: Fundamental ConceptsOne can also recall that two graphs are isomorphic if and only if theircomplements are isomorphic. The complements ofG1,G2, andG5are cy-cles of length 7, which are pairwise isomorphic. Each ofG3andG4consistsof two components that are cycles of lengths 3 and 4; these graphs areisomorphic to each other but not to a 7-cycle.•••••••••••••••••••••••••••••••••••G1G2G3G4G51.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 boundsappear below. We must prove that these constructions are smallest.•••••••••••••• •••• ••••a) generalb) looplessc) simplea) With 1 vertex, every edge is a loop, and the isomorphism class isdetermined by the number of edges, which is determined by the vertexdegree. Hence nonisomorphic graphs with the same vertex degrees haveat least two vertices.b) Every loopless graph is a graph, so the answer for loopless graphsis at least 2. The isomorphism class of a loopless graph with two verticesis determined by the number of copies of the edge, which is determinedby the vertex degrees.The isomorphism class of a loopless graph withthree vertices is determined by the edge multiplicities. Let the three vertexdegrees bea,b,c, and let the multiplicities of the opposite edges bex,y,z,where Sincea=y+z,b=x+z, andc=x+y, we can solve for themultiplicities in terms of the degrees byx=(b+c−a)/2,y=(a+c−b)/2,andz=(a+b−c)/2.Hence the multiplicities are determined by thedegrees, and all loopless graphs with vertex degreesa,b,care pairwiseisomorphic.Hence nonisomorphic loopless graphs with the same vertexdegrees have at least four vertices.c) Since a simple graph is a loopless graph, the answer for simplegraphs is at least 4.There are 11 isomorphism classes of simple graphswith 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

Loading page image...

Section 1.1: What Is a Graph?8different lists of vertex degrees (similarly for 4 edges).For 3 edges, thethree isomorphism classes have degree lists 3111, 2220, and 2211, all dif-ferent. Hence nonisomorphic simple graphs with the same vertex degreesmust have at least five vertices.1.1.24.Isomorphisms for the Petersen graph.Isomorphism is proved bygiving an adjacency-preserving bijection between the vertex sets. For picto-rial representations of graphs, this is equivalent to labeling the two graphswith the same vertex labels so that the adjacency relation is the samein both pictures; the labels correspond to a permutation of the rows andcolumns of the adjacency matrices to make them identical.The variousdrawings of the Petersen graph below illustrate its symmetries; the label-ings indicate that these are all “the same” (unlabeled) graph. The numberof isomorphisms from one graph to another is the same as the number ofisomorphisms from the graph to itself.••••••••••45122313513452413524••••••••••12522335135134412445••••••••••51244135123452134523••••••••••123452132451234135451.1.25.The Petersen graph has no cycle of length 7.Suppose that the Pe-tersen graph has a cycleCof length 7.Since any two vertices ofCareconnected by a path of length at most 3 onC, any additional edge withendpoints onCwould create a cycle of length at most 4. Hence the thirdneighbor of each vertex onCis not onC.

Loading page image...

9Chapter 1: Fundamental ConceptsThus there are seven edges fromV(C)to the remaining three vertices.By the pigeonhole principle, one of the remaining vertices receives at leastthree of these edges.This vertexxnot onChas three neighbors onC.For any three vertices onC, either two are adjacent or two have a commonneighbor onC(again the pigeonhole principle applies). Usingx, this com-pletes a cycle of length at most 4. We have shown that the assumption of a7-cycle leads to a contradiction.Alternative completion of proof.Letube a vertex onC, and letv, wbe the two vertices farthest fromuonC. As argued earlier, no edges joinvertices ofCthat are not consecutive onC. Thusuis not adjacent tovorw.Henceu, vhave a common neighbor offC, as dou, w. Sinceuhas only oneneighbor offC, these two common neighbors are the same. The resultingvertexxis adjacent to all ofu, v, w, and nowx, v, wis a 3-cycle.1.1.26.Ak-regular graph of girth four has at least2kvertices, with equalityonly forKk,k.LetGbek-regular of girth four, and chosex y∈E(G). Girth4 implies thatGis simple and thatxandyhave no common neighbors.Thus the neighborhoodsN(x)andN(y)are disjoint sets of sizek, whichforces at least 2kvertices intoG. Possibly there are others.Note also thatN(x)andN(y)are independent sets, sinceGhas notriangle. IfGhas no vertices other than these, then the vertices inN(x)can have neighbors only inN(y). SinceGisk-regular, every vertex ofN(x)must be adjacent to every vertex ofN(y).ThusGis isomorphic toKk,k,with partite setsN(x)andN(y).In other words, there is only one suchisomorphism class for each value ofk.Comment.One can also start with a vertexx, chooseyfrom amongthekvertices inN(x), and observe thatN(y)must havek−1 more verticesnot inN(x)∪ {x}. The proof then proceeds as above.(An alternative proof uses the methods of Section 1.3. A triangle-freesimple graph withnvertices has at mostn2/4 edges. SinceGisk-regular,this yieldsn2/4≥nk/2, and hencen≥2k.Furthermore, equality holdsin the edge bound only forKn/2,n/2, so this is the only such graph with 2kvertices. (C. Pikscher))•••••N(x)− {y}xN(y)− {x}•••••y1.1.27.A simple graph of girth 5 in which every vertex has degree at leastkhas at leastk2+1vertices, with equality achieveable whenk∈ {2,3}.LetGbek-regular of girth five. LetSbe the set consisting of a vertexxand

Loading page image...

Section 1.1: What Is a Graph?10its neighbors.SinceGhas no cycle of length less than five,Gis simple,and any two neighbors ofxare nonadjacent and have no common neighborother thanx.Hence eachy∈S− {x}has at leastk−1 neighbors thatare not inSand not neighbors of any vertex inS.HenceGhas at leastk(k−1)vertices outsideSand at leastk+1 vertices inSfor at leastk2+1altogether.The 5-cycle achieves equality whenk=2. Fork=3, growing the graphsymmetrically fromxpermits completing the graph by adding edges amongthe non-neighbors ofx. The result is the Petersen graph. (Comment: Fork>3, it is known that girth 5 with minimum degreekand exactlyk2+1vertices is impossible, except fork=7 and possibly fork=57.)••••••••••x1.1.28.The Odd Graph has girth 6.The Odd GraphOkis the disjointnessgraph of the set ofk-element subsets of [2k+1].Vertices with a common neighbor correspond tok-sets withk−1 com-mon elements. Thus they have exactly one common neighbor, andOkhasno 4-cycle.Two vertices at distance 2 from a single vertex have at leastk−2 common neighbors. Fork>2, such vertices cannot be adjacent, andthusOkhas no 5-cycle whenk>2.To form a 6-cycle whenk≥2, letA= {2,. . .,k},B= {k+2,. . .,2k},a=1,b=k+1,c=2k+1. A 6-cycle isA∪ {a},B∪ {b},A∪ {c},B∪ {a},A∪ {b},B∪ {c}.TheOddGraphalsoisnotbipartite.Thesuccessiveelements{1,. . .,k},{k+1,. . .,2k},{2k+1,1,. . .,k−1}, ...,{k+2,. . .,2k+1}form an odd cycle.1.1.29.Among any 6 people, there are 3 mutual acquaintances or 3 mutualstrangers.LetGbe the graph of the acquaintance relation, and letxbe oneof the people. Sincexhas 5 potential neighbors,xhas at least 3 neighborsor at least 3 nonneighbors.By symmetry (if we complementG, we stillhave to prove the same statement), we may assume thatxhas at least 3neighbors. If any pair of these people are acquainted, then withxwe have3 mutual acquaintances, but if no pair of neighbors ofxis acquainted, thenthe neighbors ofxare three mutual strangers.1.1.30.The number of edges incident toviis theith diagonal entry inM MTand inA2.In bothM MTandA2this is the sum of the squares of the entries

Loading page image...

11Chapter 1: Fundamental Conceptsin theith row. ForM MT, this follows immediately from the definition ofmatrix multiplication and transposition, but forA2this uses the graph-theoretic fact thatA=AT; i.e.columniis the same as rowi.BecauseGis simple, the entries of the matrix are all 0 or 1, so the sum of thesquares in a row equals the number of 1s in the row. InM, the 1s in a rowdenote incident edges; inAthey denote vertex neighbors. In either case,the number of 1s is the degree of the vertex.Ifi6=j, then the entry in position(i,j)ofA2is the number of commonneighbors ofviandvj.The matrix multiplication puts into position(i,j)the “product” of rowiand columnj; that is∑nk=1ai,kak,j. WhenGis simple,entries inAare 1 or 0, depending on whether the corresponding verticesare adjacent.Henceai,kak,j=1 ifvkis a common neighbor ofviandvj;otherwise, the contribution is 0. Thus the number of contributions of 1 toentry(i,j)is the number of common neighbos ofviandvj.Ifi6=j, then the entry in position(i,j)ofM MTis the number of edgesjoiningviandvj(0 or 1 whenGhas no multiple edges).Theith row ofMhas 1s corresponding to the edges incident tovi.Thejth column ofMTis the same as thejth row ofM, which has 1s corresponding to theedges incident tovj. Summing the products of corresponding entries willcontribute 1 for each edge incident to bothviandvj; 0 otherwise.Comment.For graphs without loops, both arguments for(i,j)in gen-eral apply wheni=jto explain the diagonal entries.1.1.31.Kndecomposes into two isomorphic (“self-complementary”) sub-graphs if and only ifnorn−1is divisible by 4.a) The number of vertices in a self-complementary graph is congruentto 0 or1(mod 4).IfGandGare isomorphic, then they have the samenumber of edges, but together they have(n2)edges (with none repeated), sothe number of edges in each must ben(n−1)/4. Since this is an integerand the numbersnandn−1 are not both even, one of{n,n−1}must bedivisible by 4.b) Construction of self-complementary graphs for all suchn.Proof 1(explicit construction).We generalize the structure of theself-complementary graphs on 4 and 5 vertices, which areP4andC5. Forn=4k, take four vertex sets of sizek, sayX1,X2,X3,X4, and join allvertices ofXito those ofXi+1, fori=1,2,3. To specify the rest ofG, withinthese sets letX1andX4induce copies of a graphHwithkvertices, and letX2andX3induceH. (For example,Hmay beKk.) InG, bothX2andX3induceH, whileX1andX4induceH, and the connections between sets areX2↔X4↔X1↔X3. Thus relabeling the subsets defines an isomorphismbetweenGandG. (There are still other constructions forG.)

Loading page image...

Section 1.1: What Is a Graph?12HHHHHHHHForn=4k+1, we add a vertexxto the graph constructed above. Joinxto the 2kvertices inX1andX4to formG. The isomorphism showing thatG−xis self-complementary also works forG(withxmapped to itself),since this isomorphism mapsNG(x)=X1∪X4toNG(x)=X2∪X3.Proof 2(inductive construction). IfGis self-complementary, then letH1be the graph obtained fromGandP4by joining the two ends ofP4toall vertices ofG.LetH2be the graph obtained fromGandP4by join-ing the two center vertices ofP4to all vertices ofG.BothH1andH2are self-complementary.Using this withG=K1produces the two self-complementary graphs of order 5, namelyC5and the bull.Self-complementary graphs with order divisible by 4 arise from re-peated use of the above usingG=P4as a starting point, and self-complementary graphs of order congruent to 1 modulo 4 arise from repeateduse of the above usingG=K1as a starting point. This construction pro-duces many more self-complementary graphs than the explicit constructionin Proof 1.1.1.32.Km,ndecomposes into two isomorphic subgraphs if and only ifmandnare not both odd.The condition is necessary because the numberof edges must be even.It is sufficient becauseKm,ndecomposes into twocopies ofKm,n/2whennis even.1.1.33.Decomposition of complete graphs into cycles through all vertices.View the vertex set ofKnasZn, the values 0,. . .,n−1 in cyclic order. Sinceeach vertex has degreen−1 and each cycle uses two edges at each vertex,the decomposition has(n−1)/2 cycles.Forn=5 andn=7, it suffices to use cycles formed by traversing thevertices with constant difference:(0,1,2,3,4)and(0,2,4,1,3)forn=5and(0,1,2,3,4,5,6),(0,2,4,6,1,3,5), and(0,3,6,2,5,1,4)forn=7.This construction fails forn=9 since the edges with difference 3 formthree 3-cycles. The cyclically symmetric construction below treats the ver-tex set asZ8together with one special vertex.

Loading page image...

13Chapter 1: Fundamental Concepts••••••••••••••••••••••••••••••••••••1.1.34.Decomposition of the Petersen graph into copies ofP4.Considerthe drawing of the Petersen graph with an inner 5-cycle and outer 5-cycle.EachP4consists of one edge from each cycle and one cross edge joiningthem. Extend each cross edgeeto a copy ofP4by taking the edge on eachof the two 5-cycles that goes in a clockwise direction frome. In this way,the edges on the outside 5-cycle are used in distinct copies ofP4, and thesame holds for the edges on the inside 5-cycle.Decomposition of the Petersen graph into three pairwise-isomorphicconnected 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 unchangedunder rotations of 120◦; each subgraph in the decomposition uses exactlyone edge from each class.••••••••••••••••••••••••••••••••••••••••••••••••1.1.35.Kndecomposes into three pairwise-isomorphic subgraphs if andonly ifn+1is not divisible by 3.The number of edges isn(n−1)/2. Ifn+1is divisible by 3, thennandn−1 are not divisible by 3. Thus decompositioninto three subgraphs of equal size is impossible in this case.Ifn+1 is not divisible by 3, thene(Kn)is divisible by 3, sincenorn−1is divisible by 3. We construct a decomposition into three subgraphs thatare pairwise isomorphic (there are many such decompositions).Whennis a multiple of 3, we partition the vertex set into three subsetsV1,V2,V3of equal size. Edges now have two types: within a set or joiningtwo sets. Let theith subgraphGiconsist of all the edges withinViand allthe edges joining the two other subsets. Each edge ofKnappears in exactly

Loading page image...

Section 1.1: What Is a Graph?14one of these subgraphs, and eachGiis isomorphic to the disjoint union ofKn/3andKn/3,n/3.Whenn≡1(mod 3), consider one vertexw. Sincen−1 is a multipleof 3, we can form the subgraphsGias above on the remainingn−1 ver-tices. ModifyGito formHiby joiningwto every vertex ofVi. Each edgeinvolvingwhas been added to exactly one of the three subgraphs. EachHiis isomorphic to the disjoint union ofK1+(n−1)/3andK(n−1)/3,(n−1)/3.•1.1.36.IfKndecomposes into triangles, thenn−1orn−3is divisible by 6.Such a decomposition requires that the degree of each vertex is even andthe number of edges is divisible by 3. To have even degree,nmust be odd.Alson(n−1)/2 is a multiple of 3, so 3 dividesnorn−1. If 3 dividesnandnis odd, thenn−3 is divisible by 6. If 3 dividesn−1 andnis odd, thenn−1 is divisible by 6.1.1.37.A graph in which every vertex has degree 3 has no decompositioninto paths with at least five vertices each.Suppose thatGhas such a de-composition. Since every vertex has degree 3, each vertex is an endpointof at least one of the paths and is an internal vertex on at most one ofthem. Since every path in the decomposition has two endpoints and has atleast three internal vertices, we conclude that the number of paths in thedecomposition is at leastn(G)/2 and is at mostn(G)/3, which is impossible.Alternatively, letkbe the number of paths. There are 2kendpoints ofpaths. 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 3kendpoints of paths.The contradiction impliesthat there cannot be such a decomposition.1.1.38.A 3-regular graphGhas a decomposition into claws if and only ifGis bipartite.WhenGis bipartite, we produce a decomposition into claws.We use all claws obtained by taking the three edges incident with a singlevertex in the first partite set. Each claw uses all the edges incident to itscentral vertex. Since each edge has exactly one endpoint in the first partiteset, each edge appears in exactly one of these claws.WhenGhas a decomposition into claws, we partitionV(G)into twoindependent sets.LetXbe the set of centers of the claws in the decom-position. Since every vertex has degree 3, each claw in the decomposition

Preview Mode

This document has 512 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

AP Calculus AB Unit 5 Progress Check Scoring Guide

Company

Explore

Study Tools