Discrete Mathematics for Computer Science

Introduction to Graph Theory 337 Example 1. Find the union and intersection of G and H as shown: 1 1 52 5 2 (^4) G (^3 4) H 3 So ...

338 CHAPTER 6 Graph Theory only difference is in the second position (1 and 0). An integer's binary representation can be found ...

The Handshaking Problem 339 have the same degree? Theorem 1 says that in any graph with at least two vertices, there are always ...

340 CHAPTER 6 Graph Theory We will now use this result to prove another property of graphs that can be interpreted for the hands ...

Paths and Cycles 341 joined. In some cases, this will not be a subgraph, because vertices are repeated to indicate that the trai ...

342 CHAPTER 6 Graph Theory Conditions Satisfied by Hamiltonian Graphs A Hamiltonian graph cannot contain a vertex of degree zer ...

Paths and Cycles 343 (b) First, observe that the edges (1, k), (k, j), (1, m), and (m, j) must be included in any Hamiltonian cy ...

344 CHAPTER 6 Graph Theory Now, the second edges incident to vertices 2 and 5 must be one of the following four pairs of edges: ...

Graph Isomorphism 345 W Graph Isomorphism For two graphs given abstractly as vertex and edge sets, we need to be able to determi ...

346 CHAPTER 6 Graph Theory a 1 b 6 2 e: c 5 3 d 4 G H Figure 6.17 Two nonisomorphic graphs. One way to prove that these two grap ...

Representation of Graphs 347 Since A(i, j) = A(j, i) for 1 < i, j < n, an adjacency matrix is symmetric. The diagonal entr ...

348 CHAPTER^6 Graph Theory W Exercises Find a graph with 12 edges having six vertices of degree three and the remaining vertice ...

Exercises 349 identify: (a) the degree of each vertex (b) a path of length greater than four, if any exists (c) a cycle of size ...

350 CHAPTER 6 Graph Theory Find a Hamiltonian cycle in the following graph: a bp t <^0 d h e 9 k Ir G H S f Cl' Complete t ...

Exercises 351 Prove that G and H as shown are isomorphic: 1 3 a b 2 4 e G H Prove that no pair of G 1 , G 2 , and G 3 as show ...

352 CHAPTER 6 Graph Theory joining them. List all the 3-cycles in each of the graphs (3-cycle a-b-c is counted as being differen ...

Connected Graphs 353 Definition 1. A graph for which each pair of (not necessarily distinct) vertices is joined by a trail is co ...

354 CHAPTER 6 Graph Theory to show that CONN is transitive let v, w and x be vertices of G such that v CONN w and w CONN x. Sinc ...

Connected Graphs 355 vertices and edges in different orders, but in any representation, each edge and vertex will be visited. Fi ...

356 CHAPTER 6 Graph Theory a ob Od g e h f Figure 6.23 Depth first search tree. If a graph is not connected, then the process is ...