 14.2.1: For the graph G of order n = 7 of Figure 14.30, give an example of ...
 14.2.2: For the map M in Figure 14.31, what is the minimum number of colors...
 14.2.3: (a) Determine the dual graph G of the map M in Figure 14.32. (b) De...
 14.2.4: Find a map M whose dual graph is isomorphic the connected planar gr...
 14.2.5: Determine if the following is a proof of the Four Color Theorem. Pr...
 14.2.6: Prove or disprove: If G is a graph with an odd cycle for which ther...
 14.2.7: Prove or disprove: If G is a graph with an odd cycle for which ther...
 14.2.8: Determine _(Q3).
 14.2.9: Determine the chromatic number of a nontrivial tree.
 14.2.10: Determine the chromatic number of the wheel Wn = Cn + K1 for every ...
 14.2.11: Determine the chromatic number of each of the graphs G and H of Fig...
 14.2.12: (a) For the graph G of Figure 14.35, what is the largest complete g...
 14.2.13: (a) For the graph G of Figure 14.36, what is the largest complete g...
 14.2.14: Let n 2 be an integer. (a) Show that the graph C2n+1 contains a com...
 14.2.15: Let G be a graph with V (G) = {v1, v2, . . . , vn}. A coloring of t...
 14.2.16: Eleven cities, denoted by c1, c2, . . . , c11, have applied for adm...
 14.2.17: During this coming summer, the Department of Mathematical Sciences ...
 14.2.18: Seven chemicals c1, c2, . . . , c7 are to be shipped in a number of...
 14.2.19: Figure 14.38 shows eight traffic lanes L1,L1, . . . ,L8 at the inte...
 14.2.20: For each possible positive integer k, give an example of a 4regula...
 14.2.21: Suppose that G is a graph with chromatic number k 2 and that there ...
 14.2.22: Show for every two graphs G and H that _(G + H) = _(G) + _(H).
 14.2.23: Show for every nontrivial graph G that _(G K2) = _(G).
Solutions for Chapter 14.2: Coloring Graphs
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 14.2: Coloring Graphs
Get Full SolutionsDiscrete Mathematics was written by and is associated to the ISBN: 9781577667308. This expansive textbook survival guide covers the following chapters and their solutions. Since 23 problems in chapter 14.2: Coloring Graphs have been answered, more than 12850 students have viewed full stepbystep solutions from this chapter. Chapter 14.2: Coloring Graphs includes 23 full stepbystep solutions. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1.

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

Change of basis matrix M.
The old basis vectors v j are combinations L mij Wi of the new basis vectors. The coordinates of CI VI + ... + cnvn = dl wI + ... + dn Wn are related by d = M c. (For n = 2 set VI = mll WI +m21 W2, V2 = m12WI +m22w2.)

Circulant matrix C.
Constant diagonals wrap around as in cyclic shift S. Every circulant is Col + CIS + ... + Cn_lSn  l . Cx = convolution c * x. Eigenvectors in F.

Commuting matrices AB = BA.
If diagonalizable, they share n eigenvectors.

Distributive Law
A(B + C) = AB + AC. Add then multiply, or mUltiply then add.

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.

Identity matrix I (or In).
Diagonal entries = 1, offdiagonal entries = 0.

Minimal polynomial of A.
The lowest degree polynomial with meA) = zero matrix. This is peA) = det(A  AI) if no eigenvalues are repeated; always meA) divides peA).

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

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.

Normal matrix.
If N NT = NT N, then N has orthonormal (complex) eigenvectors.

Pivot columns of A.
Columns that contain pivots after row reduction. These are not combinations of earlier columns. The pivot columns are a basis for the column space.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Rayleigh quotient q (x) = X T Ax I x T x for symmetric A: Amin < q (x) < Amax.
Those extremes are reached at the eigenvectors x for Amin(A) and Amax(A).

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Stiffness matrix
If x gives the movements of the nodes, K x gives the internal forces. K = ATe A where C has spring constants from Hooke's Law and Ax = stretching.

Symmetric factorizations A = LDLT and A = QAQT.
Signs in A = signs in D.

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.