Graph Theory - Douglas B West - 2 Ed - Ebook download as PDF File .pdf) or read book online. for ACM class, Fall soundofheaven.info Douglas B. West, Introduction to Graph Theory, China Machine. Press, This is the home page for Introduction to Graph Theory, by Douglas B. West. Inductive proof of Matrix Tree Theorem (ps pdf) without Cauchy-Binet Formula.
|Language:||English, Spanish, Japanese|
|ePub File Size:||22.64 MB|
|PDF File Size:||18.18 MB|
|Distribution:||Free* [*Regsitration Required]|
The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of the. THE RULES OF WORK A Definitive Code for Personal Success EXPANDED EDITION RICHARD TEMPLAR Browse's Introduction to the Symptoms & Signs of. Introduction to Graph Theory, by Douglas B. West. A few solutions Many students in this course see graph algorithms repeatedly in courses in.
Thus they have exactly one common neighbor, and O k has no 4-cycle. By the induction hypothesis, e G. Plus, we regularly update and improve textbook solutions based on student ratings and feedback, so you can be sure you're getting the latest information available. Assume that G is a connected even graph. Common graphs in four families: If this were possible, then we could form a graph with the teams as vertices, making two vertices adjacent if those teams play a game in the schedule.
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. The complement of a simple disconnectedgraphmust be connected— TRUE. A disconnected graph G has vertices x, y that do not belong to a path.
Hencex 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 3 Chapter 1: 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.
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. 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. Adjacent vertices have opposite parity. This graph is the k-dimensional hypercube; see Section 1. Cutting opposite corner squares froman eight by eight checkerboard leaves a subboard that cannot be partitioned into rectangles consisting of two adjacent unit squares.
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 color.
Each pair of adjacent squares has one of each color, so the remaining squares cannot be partitioned into sets of this type. Common graphs in four families: In a cycle, the numbers of vertices and edges are equal, but this is false for a path. To be a path, a graph must contain no cycle. The graphs beloware 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. There are exactly two isomorphism classes of 4-regular simple graphs with 7 vertices. 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 third graph contains odd cycles and hence is not isomor- phic to the others.
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. Isomorphism of graphs. The rightmost two graphs below are iso- morphic. The outside 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. 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. 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 1c, 2d, 3e, 4 f, 5g, 6h, 7a, 8b are also the same in both draw- ings.
Thus the two graphs have the same edges under this vertex corre- spondence. 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.
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. Isomorphism of explicit graphs. 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.
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. 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. Hence nonisomorphic graphs with the same vertex degrees have at least two vertices. 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. 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. 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 different lists of vertex degrees similarly for 4 edges. For 3 edges, the three isomorphism classes have degree lists , , and , all dif- ferent. 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 number of isomorphisms from one graph to another is the same as the number of isomorphisms from the graph to itself. 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. 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.
A k-regular graph of girth four has at least 2k vertices, with equality only for K k,k. 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 2k 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. The proof then proceeds as above.
An alternative proof uses the methods of Section 1. Let S be the set consisting of a vertex x and its neighbors. The result is the Petersen graph. The Odd Graph has girth 6.
Thus they have exactly one common neighbor, and O k has no 4-cycle. The Odd Graph also is not bipartite. 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.
The number of edges incident to v i is the i th diagonal entry in MM T and in A 2. 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. When G is simple, entries in A are 1 or 0, depending on whether the corresponding vertices are adjacent. Thus the number of contributions of 1 to entry i, j is the number of common neighbos of v i and v j.
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. 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 example, H may be K k. There are still other constructions for G. Join x to the 2k vertices in X 1 and X 4 to form G. 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. This construction pro- duces many more self-complementary graphs than the explicit construction in Proof 1.
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. Decomposition of complete graphs into cycles through all vertices. View the vertex set of K n as Z n , the values 0,.
The cyclically symmetric construction below treats the ver- tex set as Z 8 together with one special vertex. 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. Thus decomposition into three subgraphs of equal size is impossible in this case. 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: Let the i th subgraph G i consist of all the edges within V i and all the edges joining the two other subsets.
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. 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. 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.
Alternatively, let k be the number of paths. There are 2k 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 3k endpoints of paths. The contradiction implies that there cannot be such a decomposition.
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. Each claw uses all the edges incident to its central vertex. 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 15 Chapter 1: Since each edge is in at most one claw, this makes X an independent set.
The remaining vertices also form an in- dependent set, because every edge is in some claw in the decomposition, which means that one of its endpoints must be the center of that claw. Graphs that decompose K 6. A graph decomposing into triangles must have even degree at each vertex. This excludes all decompositions into cycles. Paw, P 5 —No. K 6 has 15 edges, but each paw or P 5 has four edges.
House, Bowtie, Dart—No. K 6 has 15 edges, but each house, bowtie, or dart has six edges. Each edge appears in exactly one of these claws. Put all six vertices on a circle. Three rotations of the picture complete the decomposition.
Each bull uses degrees 3, 3, 2, 1, 1, 0 at the six vertices. Thus we use vertices of two types, which leads us to position them on the inside and outside as on the right below. The bold, solid, and dashed bulls obtained by rotation complete the decomposition. Automorphisms of P n , C n , and K n. The numbers of automorphisms are 2, 2n, n! Correspondingly, the numbers of distinct labelings using vertex set [n] are n! Graphs with one and three automorphisms. The two graphs on the left have six vertices and only the identity automorphism.
The two graphs on the right have three automorphisms.
Every automorphism of the Petersen graph maps the 5-cycle 12,34,51,23,45 into a 5-cycle with vertices ab, cd, ea, bc, de by a permu- tation of  taking 1,2,3,4,5 to a, b, c, d, e, respectively. Similarly, we may select c to be the common element in the second and fourth vertices. The Peterson graph has automorphisms. Thus there are at least automorphism. By the preceding paragraph, the 5-cycle C maps to some 5-cycle ab, cd, ea, bc, de.
The remaining vertices are pairs consisting of two nonconsecutive val- ues modulo 5. The only vertex of C that 24 is adjacent to disjoint from is Since 17 Chapter 1: In the disjointness representation of the Petersen graph, suppose the pairs corresponding to the vertices of P are ab, cd, ef, g h , respectively.
A graph with 12 vertices in which every vertex has degree 3 and the only automorphism is the identity. The graph has only two triangles abc and uvw. Now d is the unique common neighbor of p and e. This construction was provided by Luis Dissett, and the argument forbidding nontrivial automorphisms was shortened by Fred Galvin. Another such graph with three triangles was found by a student of Fred Galvin.
Vertex-transitivity and edge-transitivity. The graph on the left in Exercise 1. For the graph on the right, rotation and inside-out ex- change takes care of vertex-transitivity.
One further generating operation is needed to get edge-transitivity; the two bottom outside vertices can be switched with the two bottom inside vertices. Edge-transitive versus vertex-transitive. Every edge consists of an old vertex and a new vertex.
The n! Let uv be an arbitrary edge of G.
Let S be the set of vertices to which u is mapped by automorphisms of G, and let T be the set of vertices to which v is mapped. By edge-transitivity, every edge of G contains one vertex of S and one vertex of T. The graph has some edges on triangles and some edges not on triangles, so it cannot be edge-transitive.
Statements about connection. A simple 4-vertex graph in which every vertex has degree 1 is disconnected and has no isolated vertex. If some vertex x is connected to every other, then because a u, x-path and x, v-path together contain a u, v-path, every vertex is connected to every other, and G is connected.
The vertices and edges of a closed trail form an even graph, and Proposition 1. If an endpoint v is different from the other endpoint, then the trail uses an odd number of edges incident to v. If v has even degree, then there remains an incident edge at v on which to extend the trail. Walks in K 4. A closed trail has even vertex degrees; in K 4 this requires degrees 2 or 0, which forbids connected nontrivial graphs that are not cycles. By convention, a single vertex forms a closed trail that is not a cycle.
Vertices 1,11,13 are isolated. The remainder induce a single component. It has a spanning path 7,14,10,5,15,3,9,12,8,6,4,2. Thus there are four compo- nents, and the maximal path length is Effect on the adjacency and incidence matrices of deleting a vertex or edge.
Assume that the graph has no loops. Consider the vertex ordering v 1 ,. Deleting edge v i v j simply deletes the corresponding column of the incidence matrix; in the adjacency matrix it reduces positions i, j and j, i by one. Deleting a vertex v i eliminates the i th row of the incidence matrix, and it also deletes the column for each edge incident to v i.
In the adjacency matrix, the i th row and i th column vanish, and there is no effect on the rest of the matrix. Hence v has a neighbor in each component. No cut-vertex has degree 1. The paw. Maximal paths: Maximal cliques: Maximal independent sets: A bipartite graph has a unique bipartition except for interchanging the two partite sets if and only if it is connected.
Let G be a bipartite graph. If u and v are vertices in distinct components, then there is a bipartition in which u and v are in the same partite set and another in which they are in opposite partite sets. A vertex v must be in the same partite set as u if there is a u, v- walk of even length, and it must be in the opposite set if there is a u, v-walk of odd length. The biclique K m,n is Eulerian if and only if m and n are both even or one of them is 0.
The graph is connected. It vertices have degrees m and n if both are nonzero , which are all even if and only if m and n are both even. When m or n is 0, the graph has no edges and is Eulerian. The minimum number of trails that decompose the Petersen graph is 5. The Petersen graph has exactly 10 vertices of odd degree, so it needs at least 5 trails, and Theorem 1.
Given the drawing of the Petersen graph consisting of two disjoint 5-cycles and edges between them, form paths consisting of one edge from each cycle and one edge joining them. Statements about Eulerian graphs. Every vertex has even degree. We can count the edges by summing the degrees of the vertices in one partite set; this counts every edge exactly once. Since the summands are all even, the total is also even.
Since every walk alternates between the partite sets, follow- ing an Eulerian circuit and ending at the initial vertex requires taking an even number of steps. Proof 3. Every Eulerian graph has even vertex degrees and decom- poses into cycles. In a bipartite graph, every cycle has even length. Hence the number of edges is a sum of even numbers. The union of an even cycle and an odd cycle that share one vertex is an Eulerian graph with an even number of vertices and an odd number of edges.
Paths, Cycles, and Trails 22 1. If G is an Eulerian graph with edges e, f that share a vertex, then G need not have an Eulerian circuit in which e, f appear consecutively. If G consists of two edge-disjoint cycles sharing one common vertex v, then edges incident to v that belong to the same cycle cannot appear consecu- tively on an Eulerian circuit. Algorithm for Eulerian circuit. We convert the proof by extremal- ity to an iterative algorithm.
Assume that G is a connected even graph. Initialize T to be a closed trail of length 0; a single vertex. Beginning from v along e, traversing an arbitrary trail T. Splice T. If this new trail includes all of E G , then it is an Eulerian circuit, and we stop. Otherwise, let this new trail be T and repeat the iterative step. It can only terminate when an Eulerian circuit has been found.
Each u, v-walk contains a u, v-path. We use ordinary induction on the length l of the walk, proving the statement for all pairs of vertices. A u, v-walk of length 1 is a u, v-path of length 1; this provides the basis. In each case, the edges of the u, v-path we construct all belong to W. If this is not a path, then it has a repeated vertex, and the portion between the instances of one vertex can be removed to obtain a shorter u, v-walk in W than W. The union of the edge sets of distinct u, v-paths contains a cycle.
Proof 1 extremality. Let P and Q be distinct u, v-paths. Since a path in a simple graph is determined by its set of edges, we may assume by symmetry that P has an edge e not belonging to Q. Within the portion of P before P traverses e, let y be the last vertex that belongs to Q.
The y, z-subpath of P combines with the y, z- or z, y-subpath of Q to form a cycle, since this subpath of Q contains no vertex of P between y and z. Proof 2 induction. We use induction on the sum l of the lengths of the two paths, for all vertex pairs simultaneously. If P and Q have no common internal vertices, then their union is a cycle.
If P and Q have a common internal vertex w, then let P. Since P, Q are distinct, we must have P. We can apply the induction hypothesis to the pair that is a pair of distinct paths joining the same end- points. This pair contains the edges of a cycle, by the induction hypothesis, which in turn is contained in the union of P and Q. The union of distinct u, v-walks need not contain a cycle. The distinct u, v-walks with vertex lists u, x, u, x, v and u, x, v, x, v do not contain a cycle in their union.
If W is a nontrivial closed walk that does not contain a cycle, then some edge of W occurs twice in succession once in each direction. Proof 1 induction on the length l of W. A closed walk of length 1 is a loop, which is a cycle. Basis step: Since it contains no cycle, the walk must take a step and return immediately on the same edge. Induction step: Hence there is some other vertex repetition.
Let W. By the induction hypoth- esis, W. This 23 Chapter 1: Paths, Cycles, and Trails 24 completes a cycle with e unless in fact P is the path of length 1 with edge e, in which case e repeats immediately in opposite directions.
If edge e appears an odd number of times in a closed walk W, then W contains the edges of a cycle through e. Proof 1 induction on the length of W, as in Lemma 1. The short- est closed walk has length 1. The edge e in a closed walk of length 1 is a loop and thus a cycle. If there is no vertex repetition, then W is a cycle. If there is a vertex repetition, choose two appearances of some vertex other than the beginning and end of the walk.
This splits the walk into two closed walks shorter than W. Since each step is in exactly one of these subwalks, one of them uses e an odd number of times. By the induction hypothesis, that subwalk contains the edges of a cycle through e, and this is contained in W. Let x and y be the endpoints of e.
As we traverse the walk, every trip through e is x, e, y or y, e, x. Since the number of trips is odd, the two types cannot alternate. Hence some two successive trips through e have the same direction. By symmetry, we may assume that this is x, e, y,. The portion of the walk between these two trips through e is a y, x- walk that does not contain e. By Lemma 1. Adding e to this path completes a cycle with e consisting of edges in W.
Proof 3 contrapositive. If edge e in walk W does not lie on a cycle consisting of edges in W, then by our characterization of cut-edges, e is a cut-edge of the subgraph H consisting of the vertices and edges in W. This means that the walk can only return to e at the endpoint fromwhich it most recently left e. This requires the traversals of e to alternate directions along e.
Therefore, showing that G n is connected shows that it is Eulerian if and only if n is odd. To create a v, I -path, move element 1 to the front by adjacent interchanges, then move 2 forward to position 2, and so on. This builds a walk to I , which contains a path to I. Actually, this builds a path. Proof 2 direct u, v-path. Each vertex is a permutation of [n]. The element b 1 appears in u as some a i ; move it to the front by adjacent transpositions, beginning a walk from u. Iterating this procedure brings the elements of v toward the front, in order, while following a walk.
Actually, the walk is a u, v-path. Note that since we always bring the desired element forward, we never disturb the position of the elements that were already moved to their desired positions. Proof 3 induction on n.
Every vertex of G is connected to a vertex of H by a path formed by moving element n to the end, one step at a time. By the transitivity of the connection relation, there is a u, v-path in G. This completes the proof of the induction step. The part of G 4 used in the induction step appears below. The basis is as in Proof 3. By the induction hypothesis, each such subgraph is connected. We can interchange the last two positions to obtain a neighbor in H i.
Hence there is an edge from each H i to H n , and transitivity of the connection relation again completes the proof. Thus the parity of the 25 Chapter 1: Paths, Cycles, and Trails 26 number of 1s remains the same along every edge.
This implies that G k has at least two components, because there is no edge from an k-tuple with an even number of 1s to an k-tuple with an odd number of 1s. To show that G k has at most two components, there are several ap- proaches. If u and v are vertices with the same parity, then they differ in an even number of places. This is true because each change of a bit in obtaining one label from the other switches the parity.
Since they differ in an even number of places, we can change two places at a time to travel from u to v along a path in G k. We use induction on k. G 1 has two components, each an isolated vertex. By the induction hypothesis, each subgraph has two components.
Thus the four pieces reduce to at most two components in G k. The text gives the vertex set incorrectly. All neighbors of vertex i differ from i by a multiple of k.
Thus all vertices in a component lie in the same congruence class modulo k, which makes at least k components. To show that there are only k components, we show that all vertices with indices congruent to i modk lie in one component for each i. As above, there exist integers p. If v is a cut-vertex of a simple graph G, then v is not a cut-vertex of G. Then G contains the complete multipartite graph with partite sets V 1 ,.
Hence v is not a cut-vertex of G. A self-complementary graph has a cut-vertex if and only if it has a vertex of degree 1. If there is a vertex of degree 1, then its neighbor is a cut-vertex K 2 is not self-complementary.
For the converse, let v be a cut-vertex in a self-complementary graph G. We conclude that v has degree at most 1 in G, so G has a vertex of degree at most 1. Since a graph and its complement cannot both be disconnected, G has a vertex of degree 1. A graph is connected if and only if for every partition of its vertices into two nonempty sets, there is an edge with endpoints in both sets.
Let G be a connected graph. Since G is connected, G has a u, v-path P. After its last vertex in S, P has an edge from S to T. Proof 1 contrapositive. We show that if G is not connected, then for some partition there is no edge across. In particular, if G is disconnected, then let H be a component of G. Since H is a maximal connected sub- graph of G and the connection relation is transitive, there cannot be an edges with one endpoint in V H and the other endpoint outside. Proof 2 algorithmic approach.
We grow a set of vertices that lie in the same equivalence class of the connection relation, eventually accumu- lating all vertices. Start with one vertex in S. Adding y to S produces a larger set within the same equivalence class, using the transi- tivity of the connection relation. This procedure ends only when there are no more vertices outside S, in which case all of G is in the same equivalence class, so G has only one component. Proof 3 extremality. By hypothesis, G has an edge with endpoints 27 Chapter 1: Now there is an x, v-path formed by extending an x, u- path along the edge uv.
This contradicts the choice of S, so in fact S is all of V G. Since there are paths from x to all other vertices, the transitivity of the connection relation implies that G is connected. Let v be a vertex of G. If the neighborhood of v is a clique, then since G is not complete there is some vertex y outside the set S consisting of v and its neighbors. Since G is connected, there is some edge between a neighbor w of v and a vertex x that is not a neighbor of v.
One can also use cases according to whether v is adjacent to all other vertices or not. The two cases are similar to those above. In the graph below, e lies in no such subgraph. If a simple graph with no isolated vertices has no induced subgraph with exactly two edges, then it is a complete graph. Let G be such a graph. If G is disconnected, then edges from two components yield four vertices that induce a subgraph with two edges. If G is connected and not complete, then G has nonadjacent vertices x and y.
Let Q be a shortest x, y-path; it has length at least 2. Any three successive vertices on Q induce P 3 , with two edges. Alternatively, one can use proof by contradiction.
If G is not complete, then G has two nonadjacent vertices. Considering several cases common neighbor or not, etc. Inductive proof that every graph G with no odd cycles is bipartite. Proof 1 induction on e G.
Every graph with no edges is bipartite, using any two sets covering V G. Discarding an edge e introduces no odd cycles. This forces u and v to be in opposite sets in the bipartition X, Y. Proof 2 induction on n G. A graph with one vertex and no odd cycles has no loop and hence no edge and is bipartite. When we discard a vertex v, we introduce no odd cycles. If v has neighbors u, w in both parts of the bipartition of G i , then the edges uv and vw and a shortest u, w-path in G i form a cycle of odd length.
Hence we can specify the bipartition X i , Y i of G i so that X i contains all neighbors of v in G i. A graph G is bipartite if and only if for every subgraph H of G, there is an independent set containing at least half of the vertices of H.
Every bipartite graph has a vertex partition into two independent sets, one of which must contain at least half the vertices though it need not be a maximum independent set. Since every subgraph of a bipartite graph is bipartite, the argument applies to all subgraphs of a bipartite graph, and the condition is necessary. For the converse, suppose that G is not bipartite.
By the characteri- zation of bipartite graphs, G contains an odd cycle H. This subgraph H has no independent set containing at least half its vertices, because every set consisting of at least half the vertices in an odd cycle must have two consecutive vertices on the cycle. We claim that each transposition changes the parity of the number of inversions, and there- fore each edge in the graph joins vertices with opposite parity.
Thus the permutations with an even number of inversions form an independent set, as do those with an odd number of inversions. This is a bipartition, and thus the graph is bipartite. No pairs involving elements that are before r or after s have their order changed. Thus for each such k the number of inversions changes twice and retains the same parity. This describes all changes in order except for the switch of a r and a s itself. Thus the total number of changes is odd, and the parity of the number of inversions changes.
Paths, Cycles, and Trails 30 1. Deleting the central edge leaves a bipartite subgraph, since the indicated sets A and B are independent in that subgraph. If deleting one edge makes a graph bipartite, then that edge must belong to all odd cycles in the graph, since a bipartite subgraph has no odd cycles. The two odd cycles in bold have only the central edge in common, so no other edge belongs to all odd cycles. Although these two subgraphs are isomorphic, they are two subgraphs, just as the Petersen graph has ten claws, not one.
It remains to show that we must delete at least two edges to obtain a bipartite subgraph. By the characterization of bipartite graphs, we must delete enough edges to break all odd cycles. We can do this with at most one edge if and only if all the odd cycles have a common edge. The 5-cycles b, a, c, f, h and b, d, e, g, h have only the edge bh in common. Therefore, if there is a single edge lying in all odd cycles, it must be bh. However, a, c, f, h, g is another 5-cycle that does not contain this.
Therefore no edge lies in all odd cycles, and at least two edges must be deleted. A connected simple graph not having P 4 or C 3 as an induced sub- graph is a biclique.
Choose a vertex x. Since G has no C 3 , N x is inde- pendent. Hence all of S is ad- jacent to all of N x. Powers of the adjacency matrix. The proof allows loops and multiple edges and applies without change for digraphs. By part a , A r i,i counts the closed walks of length r beginning at v i.
If this is always 0, then G has no closed walks of odd length through any vertex; in particular, G has no odd cycle and is bipartite. Conversely, if G is bipartite, then G has no odd cycle and hence no closed odd walk, since every closed odd walk contains an odd cycle. Let G i be the complete bipartite subgraph with bipartition X i , Y i , where X i is the set of vertices whose codes have 0 in position i , and Y i is the set of vertices whose codes have 1 in position i.
Given that K n is a union of bipartite graphs G 1 ,. Assign vertex v the code a 1 ,. Since every two vertices are ad- jacent and the edge joining them must be covered in the union, they lie in opposite partite sets in some G i. Therefore the codes assigned to the ver- tices are distinct.
When an even graph has more than one component, each compo- nent has a maximal trail, and it will not be an Eulerian circuit unless the 31 Chapter 1: Paths, Cycles, and Trails 32 other components have no edges. The added hypothesis needed is that the graph is connected. The proof of the corrected statement is essentially that of Theorem 1. Proof 1 induction on k. The graph G. The induction hypothesis applies to each component of G.
Any component not having odd vertices has an Eulerian circuit that contains a vertex of P; we splice it into P to avoid having an additional trail. In total, we have used the desired number of trails to partition E G. Proof 2 induction on e G. If G has an even vertex x adjacent to an odd vertex y, then G. Add xy to the trail ending at x to obtain the desired decomposition of G. If G has no even vertex adjacent to an odd vertex, then G is Eulerian or every vertex of G is odd.
The graph below has 6 equivalence classes of Eulerian circuits. If two Eulerian circuits follow the same circular arrangement of edges, dif- fering only in the starting edges or the direction, then we consider them equivalent. An equivalence class of circuits is characterized by the pairing of edges at each vertex corresponding to visits through that vertex.
A 2-valent vertex has exactly one such pairing; a 4-valent vertex has three possible pairings. The only restriction is that the pairings must yield a single closed trail. Given a pairing at one 4-valent vertex below, there is a forbidden pairing at the other, because it would produce two edge-disjoint 4-cycles instead of a single trail.
The other two choices are okay. Be- cause each circuit uses each edge, and because the reversal of a circuit C is in the same class as C, we may follow a canonical representative of the class from a along ax. We now count the choices made to determine the cir- cuit. After x we can follow one of 3 choices. This leads us through another neighbor of x to y. Now we cannot use the edge ya or the edge just used, so two choices remain. This determines the rest of the circuit.
Distinct ways of making the choices yields a distinct pairing at some vertex. Algorithm for Eulerian circuits. Let G be a connected even graph. At each vertex partition the incident edges into pairs each edge appears in a pair at each endpoint. Start along some edge. At each arrival at a vertex, there is an edge paired with the entering edge; use it to exit.
Furthermore, there is no choice in assembling this trail, so every edge appears in exactly one such trail. Therefore, the pairing decomposes G into closed trails. If there is more than one trail in the decomposition, then there are two trails with a common vertex, since G is connected. Given edges from trails A and B at v, change the pairing by taking a pair in A and a pair in B and switching them to make two pairs that pair an edge of A with an edge of B.
Now when A is followed from v, the return to A does not end the trail, but rather the trail continues and follows B before returning to the original edge. Thus changing the pairing at v combines these two trails into one trail and leaves the other trails unchanged. We have shown that if the number of trails in the decomposition ex- ceeds one, then we can obtain a decomposition with fewer trails be changing the pairing.
Repeating the argument produces a decomposition using one closed trail. This trail is an Eulerian circuit. Paths, Cycles, and Trails 34 1. Alternative characterization of Eulerian graphs. Proof 1 exhaustive counting and parity. You bet! Just post a question you need help with, and one of our experts will provide a custom solution. You can also find solutions immediately by searching the millions of fully answered study questions in our archive.
You can download our homework help app on iOS or Android to access solutions manuals on your mobile device. Asking a study question in a snap - just take a pic. Textbook Solutions. Get access now with.
Get Started. Select your edition Below by. Douglas B West. How is Chegg Study better than a printed Introduction to Graph Theory student solution manual from the bookstore? Can I get help with questions outside of textbook solution manuals? How do I view solution manuals on my smartphone?