 9.8.9.8.1: In Exercises 14 construct the dual graph for the map shown. Then f...
 9.8.9.8.2: In Exercises 14 construct the dual graph for the map shown. Then f...
 9.8.9.8.3: In Exercises 14 construct the dual graph for the map shown. Then f...
 9.8.9.8.4: In Exercises 14 construct the dual graph for the map shown. Then f...
 9.8.9.8.5: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.6: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.7: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.8: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.9: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.10: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.11: In Exercises 51 1 find the chromatic number of the given graph.
 9.8.9.8.12: For the graphs in Exercises 51 1, decide whether it is possible to...
 9.8.9.8.13: Which graphs have a chromatic number of 1 ?
 9.8.9.8.14: What is the least number of colors needed to color a map of the Uni...
 9.8.9.8.15: What is the chromatic number of Wn ?
 9.8.9.8.16: Show that a simple graph that has a circuit with an odd number of v...
 9.8.9.8.17: Schedule the final exams for Math 1 1 5, Math 1 1 6, Math 1 85, Mat...
 9.8.9.8.18: How many different channels are needed for six stations located at ...
 9.8.9.8.19: The mathematics department has six committees each meeting once a m...
 9.8.9.8.20: A zoo wants to set up natural habitats in which to exhibit its anim...
 9.8.9.8.21: Find the edge chromatic number of each of the graphs in Exercises 5...
 9.8.9.8.22: Find the edge chromatic numbers of a) Kn. b) Km,n' c) Cn. d) Wn.
 9.8.9.8.23: Seven variables occur in a loop of a computer program. The variable...
 9.8.9.8.24: What can be said about the chromatic number of a graph that has Kn ...
 9.8.9.8.25: Construct a coloring of the graph shown using this algorithm. a b c...
 9.8.9.8.26: Use pseudocode to describe this coloring algorithm
 9.8.9.8.27: Show that the coloring produced in this algorithm may use more colo...
 9.8.9.8.28: Show that Cn is chromatically 3critical whenever n is an odd posit...
 9.8.9.8.29: Show that Wn is chromatically 4critical whenever n is an odd integ...
 9.8.9.8.30: Show that W4 is not chromatically 3critical.
 9.8.9.8.31: Show that if G is a chromatically kcritical graph, then the degree...
 9.8.9.8.32: Find these values: a) X2(K3) d) X2(C5) *g) X3(C5) V2 { green, yello...
 9.8.9.8.33: Let G and H be the graphs displayed in Figure 3. Find a) X2(G). b) ...
 9.8.9.8.34: What is Xk( G) if G is a bipartite graph and k is a positive integer?
 9.8.9.8.35: Frequencies for mobile radio (or cellular) telephones are assigned ...
 9.8.9.8.36: Show that every planar graph G can be colored using six or fewer co...
 9.8.9.8.37: Show that every planar graph G can be colored using five or fewer c...
 9.8.9.8.38: Show that g(3) = I and g( 4) = 1 by showing that all triangles and ...
 9.8.9.8.39: Show that g( 5) = 1. That is, show that all pentagons can be guarde...
 9.8.9.8.40: Show that g(6) = 2 by first using Exercises 38 and 39 as well as Le...
 9.8.9.8.41: Show that g(n) 2: Ln/3J. [Hint: Consider the polygon with 3k vertic...
 9.8.9.8.42: Solve the Art Gallery proving the Art Gallery Theorem, which states...
Solutions for Chapter 9.8: Graphs
Full solutions for Discrete Mathematics and Its Applications  6th Edition
ISBN: 9780073229720
Solutions for Chapter 9.8: Graphs
Get Full SolutionsChapter 9.8: Graphs includes 42 full stepbystep solutions. Since 42 problems in chapter 9.8: Graphs have been answered, more than 33395 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073229720. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 6.

CayleyHamilton Theorem.
peA) = det(A  AI) has peA) = zero matrix.

Characteristic equation det(A  AI) = O.
The n roots are the eigenvalues of A.

Cofactor Cij.
Remove row i and column j; multiply the determinant by (I)i + j •

Echelon matrix U.
The first nonzero entry (the pivot) in each row comes in a later column than the pivot in the previous row. All zero rows come last.

Elimination matrix = Elementary matrix Eij.
The identity matrix with an extra eij in the i, j entry (i # j). Then Eij A subtracts eij times row j of A from row i.

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Full column rank r = n.
Independent columns, N(A) = {O}, no free variables.

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

Hermitian matrix A H = AT = A.
Complex analog a j i = aU of a symmetric matrix.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

Matrix multiplication AB.
The i, j entry of AB is (row i of A)·(column j of B) = L aikbkj. By columns: Column j of AB = A times column j of B. By rows: row i of A multiplies B. Columns times rows: AB = sum of (column k)(row k). All these equivalent definitions come from the rule that A B times x equals A times B x .

Normal equation AT Ax = ATb.
Gives the least squares solution to Ax = b if A has full rank n (independent columns). The equation says that (columns of A)·(b  Ax) = o.

Particular solution x p.
Any solution to Ax = b; often x p has free variables = o.

Schur complement S, D  C A } B.
Appears in block elimination on [~ g ].

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Spanning set.
Combinations of VI, ... ,Vm fill the space. The columns of A span C (A)!

Special solutions to As = O.
One free variable is Si = 1, other free variables = o.

Spectrum of A = the set of eigenvalues {A I, ... , An}.
Spectral radius = max of IAi I.

Transpose matrix AT.
Entries AL = Ajj. AT is n by In, AT A is square, symmetric, positive semidefinite. The transposes of AB and AI are BT AT and (AT)I.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).